Każde dwa wierzchołki sześciokąta foremnego połączono odcinkiem zielonym
lub czerwonym. Wykazać, że został narysowany co najmniej jeden trójkąt o bokach tego samego
koloru.
Mamy \(\displaystyle{ \frac{6(6-1)}{2}=15}\) odcinków ponieważ mamy 2 kolory (szufladki) to jednym kolorem musiało zostać namalowane co najmniej 8 odcinków. Skoro odcinków o jednakowym kolorze jest 8, a wierzchołków 6 to z jakiegoś wierzchołka wychodzą co najmniej 2 odcinki.
No i co teraz, skąd mam wiedzieć czy został utworzony trójkąt?
Ustal jeden wierzchołek grafu. Z zasady szufladkowej Dirichleta wynika, że istnieją trzy krawędzie jednego koloru (powiedzmy czerwone) wychodzące z tego wierzchołka
Czemu 3? Jak na moje to z zasady szufladkowej Dirlechta wynika, że z jakiegoś wierzchołka wychodzą conajmniej 2 krawędzie tego samego koloru. Co napisałem w pierwszym poście.
Może się mylę (+nienawidzę kombinatoryki i wszystkiego, co ma choćby powierzchowny związek z geometrią), ale skoro
Każde dwa wierzchołki sześciokąta foremnego połączono odcinkiem zielonym
lub czerwonym.
, to jak dla mnie od ustalonego przez nas wierzchołka wychodzi pięć pokolorowanych odcinków (wprawdzie dwa się pokrywają z bokami sześciokąta, ale co z tego), a jako że są tylko dwa kolory, to jest taki kolor, że pokolorowano nim trzy odcinki z tego wierzchołka wychodzące.
Dobra chyba rozumiem. Nie wiem tylko czy taki komentarz słowny wystarczy.
Z zasady szufladkowej wynika, że z jakiegoś wierzchołka wychodzą 3 krawędzie tego samego koloru. W tym momencie nie da się dobrać koloru krawędzie, by nie zamknąć jakiego trójkąta. Jeśli będziemy próbowali zamykać 2 linie tego samego koloru drugim kolorem. Potem będziemy musieli zamykać 2 linie drugiego koloru, pierwszym kolorem by nie utworzyć trójkąta. W końcu dojdziemy do momentu, że niezależnie od koloru narysowanej krawędzi zamkniemy jakieś 2 linie tego samego koloru w skutek czego utworzymy jednokolorowy trójkąt.
Skoro masz trzy linie jednego koloru wychodzące z jednego końca, to drugie końce tych linii tworzą trójkąt. By nie utworzyć trójkąta jednego koloru każdy z boków trójkąta musi być drugiego koloru. Ale wtedy cały trójkąt będzie jednego koloru.
