Jeżeli uda nam się skierować każdą z krawędzi w taki sposób, aby liczba krawędzi wychodzących z każdego wierzchołka była parzysta, to zadanie jest rozwiązane -- przy każdym z wierzchołków z osobna łączymy w pary krawędzie wychodzące jakkolwiek. Pozostaje więc udowodnić, że przy danych założeniach krawędzie można skierować w taki właśnie sposób. Skierujmy krawędzie dowolnie. Jeżeli liczba krawędzi wychodzących z każdego wierzchołka jest parzysta, to koniec. Jeżeli istnieje wierzchołek o nieparzystej liczbie, to z faktu, że liczba krawędzi jest parzysta, wynika, że istnieje również drugi taki wierzchołek. Łączymy te dwa wierzchołki ścieżką. Pozostaje zauważyć, że jeżeli na ścieżce odwrócimy skierowanie wszystkich krawędzi, to parzystość liczby wychodzących krawędzi dla wierzchołków wewnątrz krawędzi się nie zmieni, a dla krańcowych tak. Powtarzając tą procedurę wielokrotnie dochodzimy do żądanego skierowania krawędzi.
Mi jakoś beznadziejnie poszło. Wczoraj nie zrobiłam pierwszego xD ale trzecie tak. A dziś czwarte i szóste no ale za szóste może być zero. A w piątym narysowałam równoległobok ale nie wykazałam że to jest równoległobok bo robiłam to w ostatnich 5 minutach. Także do zobaczenia za rok . Próg będzie z 20.
Jestem na siebie trochę zły, że nie zrobiłem drugiego geo z pierwszego dnia.
Ogólnie to pierwsze i piąte były właściwie darmowe. Nad trzecim trzeba było chwilkę pomyśleć. Szóste było zdecydowanie najtrudniejsze, ale znajomość teorii grafów trochę pomagała. Martwię się trochę, bo mnóstwo osób pierwszego dnia mówiło "zmaksowałem, zmaksowałem", drugiego też wielu wyszło przed czasem. Jest tak co rok, czy rzeczywiście próg będzie tak wysoki??
6. W przestrzeni danych jest \(\displaystyle{ n}\) zielonych punktów, przy czym \(\displaystyle{ n \ge 4}\) i żadne cztery zielone punkty nie leżą na jednej płaszczyźnie. Niektóre odcinki łączące zielone punkty pomalowano na czerwono. Liczba czerwonych odcinków jest parzysta. Każde dwa różne zielone punkty łączy pewna łamana złożona z czerwonych odcinków. Udowodnić, że czerwone odcinki da się podzielić na takie pary, że odcinki z jednej pary mają wspólny koniec.
Treść tego zadania ma poważną wadę związaną z pogrubionym "z jednej pary".
U nas w Łodzi jeden zawodnik potraktował to dosłownie i pokazał rzecz oczywistą: Że zbiór czerwonych odcinków da się podzielić na pary w taki sposób, że w (co najmniej) jednej parze (a nie w każdej parze) oba odcinki mają wspólny koniec.
I właściwie nie ma się do czego przyczepić. W treści zadania jest mowa o jednej parze. Słowo "każda" w kontekście par w ogóle się nie pojawia.
Ostatnio zmieniony 20 lut 2016, o 22:59 przez andkom, łącznie zmieniany 2 razy.
andkom,
To bardzo ciekawe. Tym bardziej, że nie słyszałem o nikim w Warszawie, kto by na coś takiego wpadł...
Czy wiadomo już w takim razie, jak będą traktowane takie rozwiązania?
Rzeczywiście niefortunne sformułowanie, szczególnie, że ani razu nie pojawia się liczba mnoga w odniesieniu do par. Ale myślę, że wpaść na to nie było wiele łatwiej niż na poprawne rozwiązanie
andkom pisze:
Treść tego zadania ma poważną wadę związaną z pogrubionym "z jednej pary".
U nas w Łodzi jeden zawodnik potraktował to dosłownie i pokazał rzecz oczywistą: Że zbiór czerwonych odcinków da się podzielić na pary w taki sposób, że w (co najmniej) jednej parze (a nie w każdej parze) oba odcinki mają wspólny koniec.
I właściwie nie ma się do czego przyczepić. W treści zadania jest mowa o jednej parze. Słowo "każda" w kontekście par w ogóle się nie pojawia.
Wada jest oczywista i pewnie należy się max za jej wytknięcie (o ile nie jest to masowe, ale chyba nie). Za to zadanie w wersji, żeby podzielić na pary tak, by w dokładnie jednej parze odcinki mają wspólny koniec byłoby fałszywe. Więc można się przyczepić, że nie rozważono takiej interpretacji treści
Cześć! Jako nowy uczestnik Olimpiady czuję się bardzo mało wprawiony w takich zadaniach i strzelam ze moje rozumowanie było w pełni błędne ale je przedstawię, by dowiedzieć się gdzie popełniłem błąd, podobno na błędach się uczy
Ukryta treść:
Czy jeśli w zadaniu 6 stwierdzimy że założenie zawsze zachodzi dla \(\displaystyle{ n=4}\) (rozrysowałem wszystkie możliwości i w każdej dało się pozdeilić odcinki na pary o wspólnym lońcu) a następnie na mocy indukcji wykazaniu ze dla \(\displaystyle{ n+1}\) się zgadza (bo jeśli dla \(\displaystyle{ n}\) się zgadza to jest parzysta liczba odcinków, więc z naszego nowego puntu by liczba odcinków wciąż była parzysta trzeba poprowadzić parzystą liczbę odcinków, które można podzeilić na pary o wspólnym końcu w tym właśnie nowym punkcie).
Z góry dziękuję za pomoc!
Ostatnio zmieniony 21 lut 2016, o 21:34 przez Ponewor, łącznie zmieniany 1 raz.
Powód:Nieczytelny zapis - brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
Częsty błąd w dowodzie indukcyjnym: kiedy startujesz z układem \(\displaystyle{ n+1}\) punktów spełniających warunki, nie możesz założyć, że powstaje on po dodaniu do układu \(\displaystyle{ n}\) punktów spełniających warunki jednego nowego punktu. Innymi słowy, nie ma gwarancji, że usuwając jeden wierzchołek będziemy mieć dalej układ, który spełnia warunki i w efekcie nie ma jak skorzystać z założenia indukcyjnego. Np. jeżeli usuniemy wierzchołek o nieparzystej liczbie krawędzi, to zostanie nam graf o nieparzystej liczbie krawędzi. Albo możemy dostać niespójny graf.
W Toruniu z tego co widziałem nie poszło tak świetnie, chociaż nie miałem okazji kontaktu z ludźmi z samego Torunia, którzy raczej są faworytami. Ja zrobiłem 1. ,4. ,5. , co mnie zadowala jak na pierwszy start. Czy wy też odnieśliście wrażenie, że w tym roku zadania były lekko "roztrzepane"? Chodzi mi głównie o zapis w 3. i 6. Niektóre wzorcówki też mi się wydają jakieś wydziwnione.
11896 pisze:Niektóre wzorcówki też mi się wydają jakieś wydziwnione.
Istotnie, to do czego dochodzi w takiej wzorcówce do zadania 6., aby uniknąć słowa "graf" jest kompletnie absurdalne. Rozwiązanie jest zupełnie udziwnianie, idea zaciemniana i przedstawiana w niezrozumiały sposób tylko i wyłącznie po to, aby uniknąć wprowadzenie wielce trudnego pojęcia "wierzchołków i ich par" xd.
Alternatywne rozwiązanie zadania 6, w [prostym] języku teorii grafów. Wydaje mi się bardziej intuicyjne niż "firmówka".
Ukryta treść:
Rozwiązujemy przez indukcję silną (zupełną), ze względu na liczbę krawędzi. Krok indukcyjny jest następujący.
Rozważmy graf G spełniający warunki zadania. Wybieramy wierzchołek v stopnia przynajmniej dwa (jest jasne, że taki znajdziemy). Gdyby usunąć v i krawędzie do niego dochodzące, graf G rozpadłby się na pewną liczbę składowych spójności. Uwzględniamy tylko te o niezerowej liczbie krawędzi. Jeśli takich nie ma, to teza jest oczywista - mamy tylko "miotełkę". Jeśli jedna ze składowych spójności ma parzystą, niezerową liczbę krawędzi, to korzystamy z założenia indukcyjnego dla tej składowej oraz pozostałej części grafu G, która jest spójna (i niepusta). Jeśli jedna ze składowych ma nieparzystą liczbę krawędzi, to dołączamy do niej jedną z krawędzi biegnących od v. Otrzymany w ten sposób podgraf jest spójny i posiada parzystą liczbę krawędzi. Pozostała część grafu G jest również spójna i niepusta, więc znów możemy skorzystać z założenia indukcyjnego.
To jeszcze wrzutka - odkrycie wczorajsze. Zadanie 5 już zostało zidentyfikowane jako "używane".
Było użyte również (w wersji,że P i Q są na bokach, ale to niewielka różnica) na obozie w Zwardoniu 2000r. I ma tam bardzo ładny i krótki szkic rozwiązania. Polecam zadanie 11:
... n2000r.pdf
