66 miast połączonych 4 środkami transportu

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
k221
Użytkownik
Użytkownik
Posty: 83
Rejestracja: 23 sie 2015, o 15:01
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 22 razy

66 miast połączonych 4 środkami transportu

Post autor: k221 »

Mam spory problem z tym zadaniem, czy mógłby ktoś podsunąć pomysł lub rozwiązanie:

Mamy 66 miast.
Każde 2 z nich połączone są jednym z 4 środków transportu.
Wykazać, że istnieją 3 miasta, które są połączone tym samym środkiem transportu (możliwa jest podróż po trójkącie jednym środkiem)
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: 66 miast połączonych 4 środkami transportu

Post autor: a4karo »

Oznaczmy te środki transportu kolorami czarny, biały, czerwony, zielony.

Ustalmy pewne, dowolne miasto A. Z niego prowadza drogi do 65 miast, więc przynajmniej 17 z nich jest tego samego koloru (np. białego)

Gdyby któreś polączen miedzy tymi 17 miastami było białe, to mielibyśmy bialy trójkąt z A.
A jeżeli nie, to ustalmy wśród tych 17 miasto B. Z niego wychodzi 16 niebiałych połączeń, zatem przynajmniej 6 musi być czarnych... Pociagnij dalej to rozumowanie
ODPOWIEDZ