Новини
Форум
Актуално
сървърКръстева да каже мнението си че се схоласахме
Кръстева най-редовно няма интернет [!].
Но!
Сега като има ще ви сервира малко гадости [:D].
Решението вече е очевидно струва ми се, че N=5, това добре, но идеята е да се докаже, че с 4 не може, задачата е за 10 клас, може спокойно да се мине и без теория на графите, иначе сигурно би станало лесно (не съм го правила).
На практика задачата не е решена без доказването за 4 града.
Обаче ако целокупно не ви се занимава с това засега (щото ще помоля да остане отворена), ще определя даващ задача по мое усмотрение, без оглед на решил/нерешил, защото решил няма.
/Edit
А сега мисля да дам нещо като задача, хрумна ми внезапно, докато чакам да видя какво ще кажете да правим с тази [].
Както казах ще я оставим отворена, но не може никой да не дава нова заради това и за да не бавя повече ще подам топката на skynet, харесва ми чертежът му [8D], а ако откаже тогава Edin_Lud най-много заслужава правото, тъй като първи каза, че не вижда решение с по-малко от N=5.
Нова задача ще пусне Един_луд, че нещо не съм подготвен...Искам да поразгледам малко какво е било давано досега като задачи, че да не става Дежаву
Искам да помоля @Krusteva , когато си получи нета да осведоми нази - недобуталите до 10 клас, как става все-пак работата с доказването, че то няма цяла седмица да чакаме.
@Bibi показа как става с 4 пътя за 15 града, което си е доста близо до 16. [xx(]
Явно нещо не е станало съвсем ясно - горе съм обяснил (мислех си дори що годе ясно) как се доказва че не става за 16.. Права е Krusteva - теория на графите не ти трябва за тая задачка..
Айде сега колкото за спорта ще си довърша там доказателството, и да я затворим тая тема.. [8]
Начи горе в оня пост с катринката мацана на paint-a от като от първолак, има разни мисли по въпроса защо не иска с 16 града, като след прекарването на някои пътища и допускането на разни неща се стига до най-дясната картинка с три тройки независими града с максимално 1 вътрешно свързване във всяка тройка. Вземаме един град от първата тройка който не е свързан с никой друг от другите два града в същата тройка и го бележим А3. По същият начин избираме Б3 и В3. Сега А3 трябва да свържем с (евентуално) двойките градове Б12 и В12 и градовете Б2 и В3. Сега понеже А3 има останали още само 3 пътя то градовете Б2 и В3 трябва да са свързани и А3 е свързан с (само) един от тях, нека той е Б3. сега ако разгледам свързаноста на Б3 той има вече 2 излизащи пътя към А3 и В3, следователно не може да се свърже с двойките А12 и В12.. С което си докарахме противоречие и си лягаме да спим доволни..
ПП @Edin_Lud принципно почти всички дялове си искат при културното отношение към тях, използването на тежките стандартни изрази, буквичките и т.н. По същия начин ако замениш "изненадата на художника" със нещо от сорта на "използвайки аналогични съждения" ще видиш че задачката излиза.. просто мързала на художника да се обяснява до сутринта го наведе на мисълта, че и така е достатъчно ясно стига да се зазяпаш в реда в който "под заплаха от несвързаност" е чертана постъпково киартинката..
Ето и моето доказателство:
Номерирам за улеснение градовете с числата от 1 до 16, като числата нямат никакво значение (инвариантни за разсъжденията, все едно с букви или с числа, или с каквото и да е, това се вижда лесно). След като поне един град е свързан с 4 други, то нека за улеснение той да е номериран с 1 и да е свързан пряко с 2, 3, 4 и 5. Така той е напълно ‘ангажиран’ и аз ще го наричам ‘столица’, а 2, 3, 4 и 5 ще наричам ‘средни’. Тази столица обаче трябва да бъде свързана и с останалите единайсет града, които ще са ‘периферни’, което може да стане единствено посредством преминаване през среден, което от своя страна означава единадесет града пряко свързани с четири, тоест с малко Дирихле се оказва, че три средни ще бъдат свързани с по три други и за един среден ще остане да е свързан с два от единайсетте периферни.
На чертежа се вижда разположението, за което стана дума досега. Става ясно, че от средните само един град остава с възможност за построяване на връзка през него и то евентуално само с периферен град. С това приключва първият етап, в който осигурихме на столицата свързване със средните и периферните градове.
Втори етап е изграждане на връзки от всички средни към всички периферни градове. Нека разгледаме произволен среден град – например 3. За него знаем, че е свързан с центъра и всички останали средни градове, както и пряко с три периферни. С всички останали осем периферни града обаче няма връзка, а няма и възможност за изграждане на път вече, от което следва, че посредством пряко свързаните към него три периферни трябва да се свържат пряко с останалите осем. Аналогично на разсъжденията от първи етап се вижда, че два измежду 9, 10 и 11 трябва да са свързани пряко с три други периферни, а третия с двата оставащи периферни. Прилагаме същите разсъждения и за средните градове 2 и 4. За 5 нещата са по-особени – неговите два преки периферни могат да го свържат пряко сили с шест от останалите девет града, но...той има възможност за пряка връзка към един произволен периферен, принадлежащ на друг среден, нека например това да е 6 (няма значение кой ще е, всички са еднакви с оглед симетрията). 6 значи ще е точно този град, който ще е свързан с два периферни, непреки на 2 (докато 7 и 8 са с по три). Останаха да се свържат единствените два града, които имат по една свободна връзка – това са някои два периферни града, единият от които е пряко свързан с 3, другият – с 4. Така, дотук само по отношение бройката няма противоречие за изгражнето на връзки от средните към периферията. Важните изводи обаче са:
<font color="red">1.</font id="red"> 6, 7 и 8 са свързани с 9 РАЗЛИЧНИ други (осем периферни + един среден).
<font color="red">2.</font id="red"> 15 и 16 са свързани с шестте периферни, пряко свързани със средните 3 и 4 (всички РАЗЛИЧНИ).
<font color="red">3.</font id="red"> 12, 13 и 14 са свързани с осем помежду си различни периферни града + един дублиращ измежду 9, 10 или 11, с който някой от оставащите два (измежду 12, 13 или 14) вече има връзка.
<font color="red">4.</font id="red"> Аналогично на <font color="red">3.</font id="red"> за градовете 9, 10 и 11, дублиращите градове са свързани помежду си пряко задължително (в противен случай няма дублиращи градове). Точно този извод ще ми послужи да вляза в противоречие по-нататък.
Нека сега разгледаме град 6 – той е свързан с 5, а също така трябва да е свързан с още два града, единият е периферен, пряко свързан с 3, а другият пак периферен, пряко свързан с 4 (не може и двата да са свързани с периферни, пряко свързани с един и същ среден, тъй като 6 би се явил дублиращ във въпросния среден и липсващ в другия среден). Така без ограничение на общността (готин израз, нали) свързваме 6 с 9 и с 12 пряко. Така 6 е изцяло зает : 6 – 5, 9, 12. За да е свързан 6 и с 10 обаче трябва през междинен да се мине – през 5 не може, през 9 също, тъй като 9 и 10 са на един общ среден, затова остава да свържем 12 с 10. Аналогично 11 с 12 – оттук следва, че 12 е дублиращият се град в среден 4.
6 освен това трябва да се свърже и с 13 и 14 непряко – аналогични разсъждения и единствен избор : свързване пряко на 13 с 9 и на 14 с 9, от което се вижда, че дублиращия град в среден 3 е 9. Теглим чертата и се оказва, че 12 е свързан с 6, 10 и 11, а 9 е свързан с 6, 13 и 14, тоест 6 и 9 не са свързани пряко един с друг, както доказахме, че е задължително. От противоречието следва, че не е възможно подобно решение.
Доста оплетено изглежда, но всъщност е само логика, никакви формули, леми, теореми и графи, с тях може би щеше да е много по-изчистено и елегантно.
Слагам и знака, че е в историята.
