Новини
Форум
Актуално
сървърАз се предавам. Имам решение с N=5 в равнина...
Повече от това не мога да измисля. Освен това ми свърши хартията и се омазах до ушите с химикал - явно съм отвикнал да пиша [:D]
Аз се предавам. Имам решение с N=5 в равнина...
Повече от това не мога да измисля. Освен това ми свърши хартията и се омазах до ушите с химикал - явно съм отвикнал да пиша [:D]
<blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">Аз се предавам. Имам решение с N=5 в равнина...
Повече от това не мога да измисля. Освен това ми свърши хартията и се омазах до ушите с химикал - явно съм отвикнал да пиша [:D]
<div align="right">Originally posted by Edin_Lud - 22/04/2005 : 15:50:21</div id="right">
</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">
Ти вкара коня в крепостта - ще го яздиш тогава.
Аз с тримерното вече привършвам и минавам на четиримерно решение[:I]
Трябва да стане -сигурен съм!!Не се предавай още.
Трябва да докажем, че с 4 не става, иначе нищо не правим... Ама как?
Вариант 1. Да докажем, че с по 4 отсечки могат да се навържат максимум 15 града.
Вариант 2. При 16 града с 4 пътя, излизащи от всеки, имаме 32 отсечки. Да докажем, че са ни малко за да спазим условието.
Вариант 3. Да допуснем, че сме го решили с 4. И да разгледаме някой произволен град. Тогава имаме 4 други, които са на разстояние 1 от него и максимум 12, които са на разстояние 2. Да докажем, че тези 12 не могат да бъдат свързани помежду си.
Обичам да ме обичат, особено двама като вас, Wise и Edin_Lud [}].
Двумерно или тримерно - няма значение, въпрос на моделиране, ако се замислите търсите маршрути, просто отсечки...
Ако номерирате градовете от 1 до 16 на практика ще имате нещо като 1-2-3, 1-5-8, 6-10 или от рода, двойки и тройки числа, като целокупно повторяемостта на едно число във всички низове не бива да надвишава N, за което се борите.
<blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">Трябва да докажем, че с 4 не става, иначе нищо не правим... Ама как?
<div align="right">Originally posted by Bibi - 22/04/2005 : 16:08:41</div id="right">
</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">
Правим...как така да не правим.
Казваме "решението е N=5 с по-малко не става", показваме творбата и чакаме шефчето да ни покаже къде сбъркахме. Най-много да почакаме 40 часа, ако е много озлобена и упорита.
@Krusteva Аз така и не разбрах - да показвам ли как става с N=5 в 2D или решението е друго [?]
Ама показвай, и с 55 можеш да ми покажеш...ама за 4 не си ми показал нищо [] (и аз те обичам де [:P]).
Е за 5 вече стана дума - не е това!!! Лесно е!
4 гоним явно - иначе нямаше да е @Krusteva
А аз продължавам да си мисля, че не може с 4.
При система от градове с по 2 излизащи пътя от всеки, максимумът е 5 града.
Ако пътищата са по 3, получих как става за 10 града.
Предполагам, че не може да се направят 11 и че това може да се докаже.
От тук ми се чини, че за 4 пътя 15 града ще да е максимумът.
Ако се докаже, че при дадените условия за 15 града НЕ може да стане с N=4, дали следва и за 16? няма причина според мен да става по-лесна задачата, но като ми се обърква всичко...[!]
Я, аристократична загадка !
Допукаме си там противното, че с 4 няма грижи и графа е доволен, редим един от който излизат 4 бройки, земаме един който е от ония 11 дето не са от тия пет, и си викаме сега от тоз за да стигнем до оня първия явно ше требе да асфалтираме яко до някой от ония 4 дето първия до навързахме с тях.. и така 11 пъти като имаме една красота. Те в тая красота има три групи от по три градчета дет' ги назоваваме А, Б и В та единствения шанс на тия пичове е да оправят сами и да се навържат помежду си. Сега сценариите с максимален брой вътрешни вризки в тия тройки:
3) всички в групичката са с добра инфраструктура - съответно всички са изхабили 3 от 4-те си потенциални пътни настилки. Сега вързване единия с още някой от другите групи и понеже той тотално се е изхабил другите две приятелчета от неговата група трябва да му помогнат като се навържат директно към другите 5 града.. ама не става шот' те двамцата имат сборно две връзки..
2) същото като 3) само дето вързваме тоя дето е с две вътрешни към някой друг и тоя път другарчетата му имат по 2 останали шосета ама не става шот' такова.. еми ония са 5 бройки гадовете
1) тука стана интересно - сеаг гледаме тия дето нямат връзка с другарчетата си по група. Та те нямат много избор понеже трябва да пуснат тъъънки линийки към единия от всяка двойка градове от другите групи както и линия към едно от двете самотни като тях граддчета.. много приятно, но като го начертаеш за изненада на художника едното му идва нанагорно.. вярвам ясно защо..
Качам картинката и след бира две, три ще мина да ме наругаете за яснототата и к'вот там още си не харесате по отговора. [:D]
//ЕДИТ линка към минка
//ЕДИТ2 бах тоя правопис. и бирите ги дигнах на 3 [:P]
Даммм
Тва същото с "изненадата за художника" ми се случи днес докато се цапах с химикал по ръцете. Само дето не мога да го докажа, както шефчето обича, с буквички и числа. Та не знам сега теория на графите признава ли небуквени (без X, Y, N, K, алфа, гама) доказателства или не. Тая математика ми е непозната /както и другата установявам в последно време...а га бееме млади бееме приятелчета...но това е една друга тъжна тема/
//ЕДИТ: м/у другото днес намерих начин да вържа 12 града с макс 4 шосета от всеки град и ми е интересно дали може повече от 12. Ако някой се вълнува как се свързват, ще го изографисам и ще го постна
Мисля, че е това: N=5 - обаче нямам нерви да го проверя добре - напълно се сдухах - гледам телевизия и мислено прекарвам диагонални линни и успоредници през кинескопа...:-(
При N=4 няма начин да стане освен ако не се опита с изкривяване на пространството.
<blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">
Ако номерирате градовете от 1 до 16 на практика ще имате нещо като 1-2-3, 1-5-8, 6-10 или от рода, двойки и тройки числа, като целокупно повторяемостта на едно число във всички низове не бива да надвишава N, за което се борите.
<div align="right">Originally posted by Krusteva*-*22/04/2005*:* 16:13:08</div id="right">
</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">
Не съм съгласен! Пример:
1-2-3
1-2-4
1-2-6
2 се повтаря 3 пъти, но е свързан с 4 други града.
<blockquote id="quote"><font size="1" id="quote"><b id="quote">quote:</b id="quote"></font id="quote"><table border="0" id="quote"><tr id="quote"><td class="quote" id="quote"><font size="1" id="quote">
Имате 16 града и следната задача : трябва да се построят пътища между градовете, така че от всеки град да се стига до произволен друг или пряко, или чрез преминаване през един междинен град, като от всеки град да <font color="red">излизат</font id="red"> най-много N пътища, като N е минималното възможно число, изпълняващо условието. Колко е N?
</td id="quote"></tr id="quote"></table id="quote"></blockquote id="quote"><font size="2" id="quote"></font id="quote">
Не знам дали трябва да приемаме, че пътищата са двупосочни - все пак това си е допълнително разхищение на асфалт. [:D]
Мисля, че това, което Key казва е вярно.
Точно по този начин открихме решението с максимум 5 пътя от всеки град.
Но вярвам, че има и по-елегантно доказателство.
Krysteva има предвид да броим в колко отсечки от онези поредици участва всяко число. 1-2-3 са две отсечки, така че 1 и 3 участват по веднъж, а 2 - два пъти.
Ако посочим 32 двойки, такива, че всяко от числата от 1 до 16 да участва в 4 от тях, а за всяка двойка А,В, която не е в списъка ни, да съществува число Х, така, че да имаме А-Х и В-Х в списъка, ще сме готови. Или с принципа на Дирихле да покажем, че това няма как да стане.
Обаче този начин не мога да го реализирам.
Мисля, че добрия път за доказването минава през подграфи.
За задачата с 3 пътя максимумът е точно 10 града.
С 10 имам решение, а с повече от 10 няма как да стане, защото ако вземем един от тях, той има три съседни, всеки от които води до най-много 2 ново града. Общо 10. А 11-ти няма как да бъде достигнат.
Така че, ако допуснем, че сме решили задачата с 16 града и 4 пътя от всеки и премахнем по подходящ начин 5 града, заедно с пътищата, излизащи от тях, стигаме до задача с 11 града (за която вече знаем, че е невъзможна).
Но не успявам до момента да махна 5 града така, че да съм в състояние да гарантирам за останалите, че са свързани и имат по 3 пътя от всеки.
//EDIT
Ето как става задачата, ако градовете бяха 15:
1-2, 1-7, 1-10, 1-15, 2-3, 2-5, 2-14, 3-4, 3-9, 3-15,
4-5, 4-7, 4-13, 5-6, 5-11, 6-7, 6-9, 6-12, 7-8, 8-9,
8-11, 8-14, 9-10, 10-11, 10-13, 11-15, 12-13, 12-14, 12-15, 13-14.
С 5 пътя могат да се навържат 24 града, така че проблемът за 16 още стои.
