III et. I OMG - kolorowanie odcinków

[patry93]

Witam

W przestrzeni danych jest takich \(\displaystyle{ n}\) punktów (\(\displaystyle{ n qslant 4}\)), że żadne cztery nie leżą na jednej płaszczyźnie. Każde dwa z tych punktów połączono odcinkiem niebieskim lub czerwonym. Udowodnij, że można tak wybrać jeden z tych kolorów, aby każde dwa punkty były połączone odcinkiem lub łamaną wybranego koloru.

Nie bardzo wiem jak to zadanie ruszyć :/
Czy to może trzeba zrobić z Dirichleta?

Z góry dziękuję za pomoc.

[Sylwek]

Dla n=4 teza jest prawdziwa (proste przypadki). Następnie indukcja: załóżmy. że teza jest prawdziwa dla naboru k punktów (dla ustalenia uwagi są one połączone kolorem niebieskim). Krok indukcyjny: gdyby k+1-szy punkt był połączony z dowolnym innym punktem odcinkiem koloru niebieskiego, to teza jest prawdziwa, w przeciwnym przypadku jest połączony z każdym innym punktem odcinkiem koloru czerwonego, zatem każde dwa punkty są połączone odcinkiem/łamaną koloru czerwonego, co kończy krok indukcyjny.

[patry93]

Sylwek - dziękuję za pomoc, ale ja oczywiście tępy być i nie do końca rozumieć :/
Nie wiem czy do końca rozumiem samą treść zadania i czy chodzi tutaj tak naprawdę o to, że "musi istnieć droga jednego koloru przechodząca przez wszystkie punkty"?

Dla n=4 teza jest prawdziwa (proste przypadki)

Tzn. mam rozważyć przypadki graficznie czy słownie, oraz czy trzeba wszystkie możliwe sposoby rozmieszczenia kolorów na odcinkach rozpatrzyć?
Wtedy będzie chyba "aż" 6 przypadków?

Następnie indukcja

Czy indukcja to "uniwersalny i dobry" sposób na tego typu zadania?

załóżmy. że teza jest prawdziwa dla naboru k punktów

Czyli tylko dla k punktów, ale bez tych "pierwszych" czterech?

gdyby k+1-szy punkt był połączony z dowolnym innym punktem odcinkiem koloru niebieskiego, to teza jest prawdziwa, w przeciwnym przypadku jest połączony z każdym innym punktem odcinkiem koloru czerwonego, zatem każde dwa punkty są połączone odcinkiem/łamaną koloru czerwonego

Hm.... ale dlaczego nie rozważasz w ogóle przypadków gdy np. odcinki są pokolorowane "chaotycznie" tzn. nie tak jak u Ciebie - "wszystkie niebieskie, albo wszystkie czerwone"? Wtedy przecież upraszczasz sobie zadanie nie pisząc dlaczego tak można, a zadanie ma być udowodnione dla dowolnych (nieregularnych) pokolorowań....

[Sylwek]

Tzn. mam rozważyć przypadki graficznie czy słownie, oraz czy trzeba wszystkie możliwe sposoby rozmieszczenia kolorów na odcinkach rozpatrzyć?
Wtedy będzie chyba "aż" 6 przypadków?

Można na różne sposoby, chyba choć jeden powinieneś znaleźć - np. z punktu A wychodzą dwa odcinki jednego koloru, ustalmy: AB, AC, które są niebieskie, jak AD lub BD lub CD jest niebieski, to koniec, jak nie, AD, BD i CD są czerwone, zatem tworzą one poszukiwaną sieć.

Czy indukcja to "uniwersalny i dobry" sposób na tego typu zadania?

Często tak

Czyli tylko dla k punktów, ale bez tych "pierwszych" czterech?

Nie, poczytaj o indukcji matematycznej

Hm.... ale dlaczego nie rozważasz w ogóle przypadków gdy np. odcinki są pokolorowane "chaotycznie" tzn. nie tak jak u Ciebie - "wszystkie niebieskie, albo wszystkie czerwone"? Wtedy przecież upraszczasz sobie zadanie nie pisząc dlaczego tak można, a zadanie ma być udowodnione dla dowolnych (nieregularnych) pokolorowań....

Z założenia k punktów tworzy sieć jednego koloru (niebieskiego). Zatem z każdego z tych k punktów wychodzi co najmniej jeden odcinek niebieski. Zatem gdyby ten k+1-szy punkt był połączony z dowolnym innym odcinkiem koloru niebieskiego, zatem "dołączyłby się" do sieci niebieskiej, w przeciwnym wypadku każdy inny punkt byłby połączony z tym k+1-szym punktem odcinkiem koloru czerwonego, zatem wszystkie punkty tworzyłyby sieć czerwoną.


Najpierw 10x przeczytaj mój dowód i spróbuj sam dociec, dlaczego akurat tak, dopiero pytaj, użyłem kilku mało znaczących skrótów myślowych, ale nie powinno być problemu ze zrozumieniem.