Регистрирайте сеРегистрирайте се

Обобщен вариант на 1 задача от ТНГ 09 пролетен тур


 
   Форум за математика Форуми -> Олимпиади и състезания за 9-12 клас
Предишната тема :: Следващата тема  
Автор Съобщение
Пафнутий
VIP


Регистриран на: 04 Mar 2008
Мнения: 1199

Репутация: 137.7
гласове: 54

МнениеПуснато на: Wed Jul 15, 2009 2:49 pm    Заглавие: Обобщен вариант на 1 задача от ТНГ 09 пролетен тур

Дадена е таблица [tex]N[/tex] x [tex]N[/tex][tex](N\in\mathbb{N})[/tex].Върху някои от квадратчетата на таблицата е поставен знакът "завой",а на произволно нейно квадратче - шахматната фигура къща.Шахматната фигура автомобил влиза в таблицата от произволно нейно крайно квадратче и се движи към вътрешноста и по същия ред/стълб. Преминавайки през квадратче със знак "завой", тя променя посоката си с [tex]90^{\circ}[/tex] и продължава да се движи праволинейно. Възможно ли е по такъв начин да се поставят знаците "завой" и къщата, че да не е възможно автомобилът да отиде на същото квадратче, където се намира и къщата.
Забележка: Оригиналната задача е с [tex]n=101[/tex] и къщата е поставена в центъра на квадратната таблица.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Реклама







Пуснато на:     Заглавие: Реклама

Върнете се в началото
Saposto_MM
Напреднал


Регистриран на: 02 Apr 2007
Мнения: 383
Местожителство: Панагюрище
Репутация: 124.4
гласове: 67

МнениеПуснато на: Thu Jul 16, 2009 10:53 am    Заглавие:

Не! Задължително от двете страни на къщата по реда и стълба, в който се намира, трябва да има знак завой. Иначе колата ще може директно да стигне до нея. Да изберем един от тези 4 знака и да разсъждаваме върху него. Нека б.о.о. това да е този, който се намира в стълба на къщата и "под" нея. За да не може колата да мине през този знак по пътя си към къщата от двете страни в реда в който се намира този знак също трябва да имаме знаци, иначе колата влиза в реда, в който се намира избрания от нас знак и като мине през него свива на дясно към къщата. Същото разсъждение можем да приложим и за двата новодобавени знака. След това и за тези два нови знака правим същите разсъждения и продължаваме нататък. Но понеже дъската е крайна, то за някой знак, след краен брой прилагания на горното разсъждение, няма да можем да сложим нови два знака защото бихме излезли от дъската (дори само един знак да не можем да сложим е достатъчно). Така този знак няма да може да бъде "защитен" от колата, и понеже той защитава друг знак от нея, пък този "друг" защитава следващ и така нататък, ще се получи нещо като "верижна реакция", и колата ще достигне до къщата. Тук е добре да се каже, че не може да съществува затворен цикъл от знаци, който са защитават взаимно, защото е ясно, че ако вземем някой краен от тях (някой от изпъкналата обвивка на множеството от клетки, в който се намират тези знаци) той няма да се бъде защитен от никой от поне една страна на негов ред или стълб. Така като минем през този знак ще можем да стигнем до друг знак от изпъкналата обвивка, а през този друг вече ще можем да стигнем до знак от по-долен слой на тази съвкупност от знаци (слой който е по-близо до къщата). Като продължим така ще можем да стигнем до знаци който са непосредствено преди къщата. И значи ще можем да стигнем до нея.

Това решение определено не е добре описано. Честно казано изпитвам затруднения да напиша по-математическо на тази задача.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Пафнутий
VIP


Регистриран на: 04 Mar 2008
Мнения: 1199

Репутация: 137.7
гласове: 54

МнениеПуснато на: Thu Jul 16, 2009 11:24 am    Заглавие:

Браво! Аз я решавам по същият начин. Описването ми, разбира се, малко се различава (построявам редица от завои [tex]a_{1},...a_{s}[/tex], която винаги ни довежда до къщата).Според мен, всъщност съществуват най-малко 4 различни пътя, водещи ни до къщата.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
martosss
VIP Gold


Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
Репутация: 424.2Репутация: 424.2
гласове: 213

МнениеПуснато на: Thu Jul 16, 2009 12:55 pm    Заглавие:

Пацул написа:
Според мен, всъщност съществуват най-малко 4 различни пътя, водещи ни до къщата.
Съгласен съм с твоето мнение. Ако всичко е празно, то пътищата са 4, ако започнем да слагаме завои(на правилните места) може само да увеличим броя на пътищата.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Пафнутий
VIP


Регистриран на: 04 Mar 2008
Мнения: 1199

Репутация: 137.7
гласове: 54

МнениеПуснато на: Thu Jul 16, 2009 4:44 pm    Заглавие:

Ето го и моето решение, което като идея не се различава от това на ММ:
Ще докажем, че винаги съществува път, отвеждащ ни до къщата, независимо от разположението на знаците.Да отбележим, че е ясно, че ако къщата е в някой от крайните редове или стълбове то до нея се стига. Затова ще разглеждаме другия случай- когато тя е вътре. Ясно е, че има поне един завой от 2-те страни на къщата в съответния ред/стълб на къщата. Означаваме най-близкият завой отляво на къщата в същия ред с [tex]A_{1}[/tex]. Дефинираме сега редицата [tex]\{A_{i}\}_{i=1}^s[/tex] от завои по следния начин:
[tex]1)[/tex] [tex]A_{i+1}[/tex] е най-близкия завой отляво на [tex]A_{i}[/tex] от същия ред при четно [tex]i[/tex].
[tex]2)[/tex] [tex]A_{i+1}[/tex] e най-близкият завой отгоре на [tex]A_{i}[/tex] от същия стълб при нечетно [tex]i[/tex].
Ако някой от тези завой не съществува, то е ясно, че се достига до къщата.Очевидно, понеже таблицата е крайна, ще съществува такова [tex]k[/tex] и нека то да е най-малкото с това с-во, че [tex]A_{k}[/tex] да лежи в краен ред/стълб. Б.О.О [tex]A_{k}[/tex] лежи на най-левия стълб на таблицата. Ако [tex]k[/tex] е четно, то автомобилът влиза в таблицата в това квадратче и очевидно пътя [tex]A_{k}...A_{1}[/tex] го отвежда до къщата.Ако пък [tex]k[/tex] е нечетно, то дефинираме [tex]A_{k+1}[/tex] според [tex]1)[/tex] и тогава [tex]A_{k+1}..A_{1}[/tex] ни отвежда до къщата. Ако пък този завой не съществува, то навлизаме с автомобилът в най-левия стълб отгоре и пътя [tex]A_{k}...A_{1}[/tex] е търсеният. Остава само да отбележим, че автомобилът наистина може да се движи по тези пътища.
ПП По горния начин лесно се доказва всъщност, че търсените пътища са повече, ако къщата не лежи на краен ред/стълб.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Олимпиади и състезания за 9-12 клас Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

 
Идете на:  
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
Може да прикачвате файлове
Може да сваляте файлове от този форум
Copyright © 2005-2020 math10.com.