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)
66 miast połączonych 4 środkami transportu
-
- 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
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
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