Зимни математически състезания - Пловдив, 2013

[Гост]

Никой ли в този форум не е участвал в Пловдив тази година?! Или просто не ви пука?!

[Гост]

Искаш да кажеш: "в Ямбол".

[Mr.G{}{}Fy]

Зимните бяха в Пловдив.В Ямбол ще са Пролетните за по-големите ученици.

[Гост]

http://www.minedu.government.bg/opencms ... a-temi.pdf

[Гост]

kak minaha sastezaniqta po matematika,dobro li beshe predstavqneto?

[drago]

Tова по-долу е инструкцията за оценяване на зад. 10.4 /4-та за 10 клас/.

10_4.png (37.98 KiB) Прегледано 931 пъти

Не ви ли амбицира да намерите решение без индукция?
Хайде да помислим..., има много хубаво решение без изпозване на индукция !!

[drago]

На езика на графите: имаме граф [tex]G[/tex] с [tex]n[/tex] върха и повече от [tex]\frac{3}{2}(n-1)[/tex] ребра. Да се докаже, че има 2 върха: [tex]x,y[/tex] , така че да има 3 непресичащи се пътя между [tex]x[/tex] и [tex]y[/tex].

Не е задължително графа [tex]G[/tex] да е свързан. Той може да има няколко свързани компоненти [tex]G_i\, i=1,\ldots,k[/tex] , всеки с [tex]v_i[/tex] брой върхове и [tex]e_i[/tex] на брой ребра, то поне за 1 от тях [tex]G_j[/tex] е в сила [tex]e_j > \frac{3}{2}(v_j - 1)[/tex]. Защо ? Ами защото, ако допуснем, че това не е така и за всяко [tex]i[/tex] имаме: [tex]e_i \leq \frac{3}{2}(v_i - 1)[/tex] , то ако съберем тези неравенства ще получим противоречие с условието. Всичко това показва, че спокйно може да считаме, че [tex]G[/tex] e свързан. В този случай е известен фактът, че може да изтрием част от ребрата на [tex]G[/tex], така че останалият граф е дърво и съдържа всички върхове на [tex]G[/tex]. Това дърво се нарича spanning tree на [tex]G[/tex] и да го означим с [tex]T[/tex] . На български може би трябва да се нарича покриващо дърво, но използвам англисйкия термин тъй като се е наложил абсолютно покрай приложението му в компютърните мрежи(spanning tree protocol на OSI модела, напр. всеки switch го има вграден ). Има много методи за построяване на spanning tree, но за това малко по-долу.
Всяко дърво, в частност [tex]T[/tex], има [tex]n-1[/tex] ребра- това е известно твърдение, простото му доказателство може да намерите например в Graph theory на Reinhard Diestel- една превъзходна книга, първите няколко глави, на която трябва да се изчетат подробно от всеки състезател със сериозни намерения.
Продължаваме- тъй като ребрата от [tex]G[/tex], които не са от [tex]T[/tex] са повече от [tex]\frac{n-1}{2}[/tex] , то има поне 2 от тях с общ връх.
Сега трябва да видим, че ако добавим в [tex]T[/tex] още две ребра излизащи от един и същ връх ще получим три пътя между 2 върха. Нека [tex]v \in T[/tex] и сме добавили още две ребра [tex]vu[/tex] и [tex]vw[/tex], [tex]u,w \in V(T)[/tex] (върховете на T) . Нека [tex]vu_1u_2\ldots u[/tex] и [tex]vw_1w_2\ldots w[/tex] са пътищата в [tex]T[/tex], които свързват съответно [tex]v[/tex] с [tex]u[/tex] и [tex]v[/tex] с [tex]w[/tex] (те са единствени-виж в горната книга). Ако [tex]u_1[/tex] съвпада с [tex]w_1[/tex] , работата е ясна, просто си начертайте едно дърво и от един връх добавете още 2 ребра така че в началото да са от един клон и ще видите.
Обаче е възможно [tex]vu_1u_2\ldots u[/tex] и [tex]vw_1w_2\ldots w[/tex] да са непресичащи се пътища. Тогава духаме супата.

Как може да избегнем тази ситуация. Можем ли да построим такова spanning tree (ST) на [tex]G[/tex] , че да я изключим?!
Най-известния начин за построяване на ST е с т.н. depth-first-search алгоритъм. Това е алгоритъма за преброждане на лабиринт. Тръгваме от един връх по [tex]G[/tex] произволно завивайки, докато не стигнем вече посетен връх. Тогава се връщаме един връх назад и тръгваме към непосетен връх и продължаваме нататък, ако няма непосетен връх връщаме се още назад и т.н. докато посетим всички върхове на първоначалния граф. Това ST има много хубави свойства, но не ни гарантира това, което търсим.
Другият алгоритъм е breadth-first search. Tръгваме от произволен връх [tex]v_0[/tex] и избираме всички ребра излизащи от този връх. Вземаме един от върховете, край на едно от тези ребра, и присъединяваме всички излизащи от него ребра, които не завършват с вече присъединен връх и т.н. При този алгоритъм, дървото [tex]T[/tex], което се получава има едно хубаво свойство: да вземем един произволен връх [tex]v[/tex] на дървото. Ако съществува ребро [tex]vu[/tex] на G, което не принадлежи на T, то обезателно [tex]u[/tex] е по-близо до началото [tex]v_0[/tex] , отколкото [tex]v[/tex] , като пътя от [tex]v_0[/tex] до [tex]v[/tex] в [tex]T[/tex] минава през [tex]u[/tex]. Eто това ни гарантира , че ситуацията описана по-горе не може да се случи.

Мисля, че това решение е конструктивно и например лесно може да се адаптира на програма, която намира тези 2 върха и 3-те непресичащи се пътища, които ги свързват.

Колко точки би получил състезател намерил това решение? Според инструкцията: "1 т. за опростяването, че графът е свързан и всички върхове са от степен поне 2"
Да не говорим, че твърдението "всички върхове са от степен поне 2" просто не е вярно !!

[drago]

Както казваше един мой преподавател- във всяко доказателство има поне една (несъществена) грешка.
И тъй като не мога да си го оправя- (към администратора: какъв е смисъла на тази политика да не мога да си редактирам по-стари постове)- ще трябва да напиша опровержение и как трябва да се чете:

Най-долу в предния ми пост това:
"При този алгоритъм, дървото , което се получава има едно хубаво свойство: да вземем един произволен връх [tex]v[/tex] на дървото. Ако съществува ребро [tex]vu[/tex] на [tex]G[/tex], което не принадлежи на [tex]T[/tex], то обезателно [tex]u[/tex] е по-близо до началото [tex]v_0[/tex], отколкото [tex]v[/tex] , като пътя от [tex]v_0[/tex] до [tex]v[/tex] в [tex]T[/tex] минава през [tex]u[/tex] ."
трябва да се чете така:
"... да вземем един произволен връх [tex]v[/tex] на дървото [tex]T[/tex]. Нека [tex]v^{-}[/tex] e предходния на [tex]v[/tex] връх в [tex]T[/tex] в посока началото [tex]v_0[/tex] . Тогава ако съществува ребро [tex]vu[/tex] на [tex]G[/tex] , което не принадлежи на [tex]T[/tex] , то пътя от [tex]v[/tex] към [tex]u[/tex] в [tex]T[/tex] минава през [tex]v^{-}[/tex]. T.e. не може да има ребро на [tex]G[/tex] , което свързва [tex]v[/tex] с връх, който е след [tex]v[/tex], гледано от началото [tex]v_0[/tex]. Tова го гарантира просто алгоритъма на построяване на [tex]T[/tex]."

[drago]

Интересно, като търсех нещо в книжката на Laszlo Lovasz "Combinatorial Problems and Exercises"(1979) намерих това:

10.4.png (75.84 KiB) Прегледано 824 пъти

Ограденото е точно зад. 10.4, под нея съм вмъкнал решението, дадено в книгата. Цитираната 6.33б е друга задача от тази книга, на която се позовава решението. Всъщност това е характеризация на 2-свързаните графи и можете да го намерите в R. Diestel като proposition 3.1.2 в 3-та глава.
Това е по-близко до официалното решение по индукция.

[drago]

Понеже ми стана интересно, пуснах я и в арт-а.
Ето още едно решение: http://www.artofproblemsolving.com/Foru ... 2&t=520148
Някаква вариация на индукцията от брошурата от състезанието.

Тази година задачите от ЗМС ми харесаха. Ако трябва да ги подредя по трудност, в намаляващ ред: 11.4 ; 10.4 ; 9.4 ; 12.4 .
Протоколите от оценяването са показателни: всяка от тези задачи е решена от не-повече от 2-3 състезатели. Задача 11.4 не е направена от никой, максималния брой точки е 3, като само един състезател има толкова, ако помня добре.
Бих казал, че участниците можеха да имат много повече успех на 10.4 и 9.4, ако бяха се запознали с няколко глави от теория на графите. Няма начин, без знание няма успехи.

[drago]

Бих искал да изкоментирам и задачите 11.4 и 9.4, но нямам време през седмицата. 9.4 е рутинна, ако човек е запознат с основни факти от теорията на ориентираните графи. Всъщност може би тя и така е измислена, като след това е намерено по-директно решение, предвид и на по-опростената хипотеза.
11.4 е може би най-трудната и интересна. даденото решение е много поучително и е пример как като обобщим нещо може да го направим по-лесно за атакуване.
Въпреки това ми се щеще да намеря и малко по-мотивирано и директно решение без използване на индукция.
Но ще ми трябва време да го напиша.

[Гост]

9.4 е рутинна, ако човек е запознат с основни факти от теорията на ориентираните графи. Всъщност може би тя и така е измислена, като след това е намерено по-директно решение, предвид и на по-опростената хипотеза.

9.4б) Възможно ли е този брой да се дели на 7?

[drago]

Постановката е такава. Имаш един ориентиран граф. За него се казва, че е силно свързан, ако за всеки два върха x,y може да се отиде от x в y , като не се движиш в "насрещното" движение. например ориентиран граф, в който има пълен (ориентиран) цикъл е такъв. Ако имаш ориентиран граф, и той е силно свързан, то в него обезателно има (ориентиран) цикъл. Това е теорема. Нещо повече, ako това е пълен ориентиран граф (tournament) има цикли с всевъзможна дължина. Всеки ориентиран граф се разбива на максимални силно свързани компоненти, като не може да тръгнеш от даден компонент и пак да се върнеш в него, защото иначе ще получиш по-голям компонент. В нашия случай всички компоненти са с брой върхове [tex]\leq 4[/tex], т.е.1,3,4 и характеристиката на графа е такава: графа се разбива на tournament-и [tex]A_1, A_2,\ldots, A_n , \, |A_i| \leq 4[/tex] , като ребрата между тези компоненти са насочени от по-малкия към по-големия индекс. Възможните пътища вътре в един компонент с три върка са винаги 3, а в такъв с 4 върха- винаги 5, без значение как са ориентирани ребрата вътре.
Така че броя на пътищата, които минават през всички върхове е [tex]3^r5^s[/tex] , където r и s са броя на компонентите с 3 и 4 върха.

[drago]

Още малко коментар по задача 11.4. Както се оказва, това също е класически резултат от теория на графите.
Зад. 11.4. Даден е граф [tex]G[/tex] с [tex]2n[/tex] върха. За всеки [tex]n[/tex] върха на [tex]G[/tex] съществува връх на графа свързан с всички тях. Какъв е минимално възможния брой ребра на [tex]G[/tex].

Първо малко терминология. Едно множество от върхове [tex]U[/tex] в един граф се нарича доминиращо, ако всеки връх на графа е или във [tex]U[/tex] или е свързан с връх от [tex]U[/tex]. Доминиращо число [tex]\gamma(G)[/tex] на даден граф [tex]G[/tex] е възможно най-малкия брой върхове, които образуват доминиращо множество.
Да допуснем сега, че [tex]G[/tex] удовлетворява условията на задачата. Toгава за всяко подмножество от [tex]n[/tex] върха съществува връх несвързан с тях. За допълнителния граф [tex]\overline{G}[/tex] на [tex]G[/tex] това ще ознчачава, че за всяко подможество от [tex]n[/tex] върха на [tex]\overline{G}[/tex] има връх от [tex]\overline{G}[/tex] несвързан с всички тях. Това означава, че [tex]\gamma(\overline{G}) \geq n+1[/tex].
Сега използваме една теорема на Визинг: Граф [tex]G[/tex] с [tex]m[/tex] върха и доминиращо число [tex]\gamma[/tex] има най-много [tex]\frac{(m-\gamma)(m-\gamma+2)}{2}[/tex] ребра.
Прилагане тази теорема към [tex]\overline{G}[/tex]... Повече, както и доказателството на тази теорема вижте тук: http://www.artofproblemsolving.com/Foru ... 2&t=520271

[Гост]

9.4б) Възможно ли е този брой да се дели на 7?

9.4в) Да се докаже, че във всеки турнир броят на възможните пътеки, образувани от всички играчи, е нечетно число.