4. Zadatak
Šest otoka povezano je linijama jednog trajektnog i jednog hidrogliserskog poduzeća. Svaka dva otoka povezana su (u oba smjera) linijom točno jednog od ova dva poduzeća. Dokaži da je moguće ciklički posjetiti četiri otoka koristeći linije samo jednog poduzeća (tj. da postoje četiri otoka , , i i poduzeće čiji brodovi plove na linijama , , , ).
Rješenje
Broj linija između 6 otoka je . Prema Dirichletovom načelu postoji poduzeće, nazovimo ga , koje plovi na barem 8 linija. Promotrimo četveročlane podskupove otoka i za svaki takav podskup promotrimo sve linije između ta 4 otoka kojih ima . U barem jednom od tih podskupova na 4 linije plovi , s obzirom da to poduzeće plovi na više linija od drugog poduzeća. Naime, u protivnom bi za svaki četveročlani podskup na po 3 linije plovilo i jedno i drugo poduzeće, što nije moguće.
Ako te 4 linije čine ciklus, tvrdnja je dokazana.
Pretpostavimo sada da plovi između otoka , , i na točno 4 linije koje ne čine ciklus (ako bi plovio na 5 linija među tim otocima, tada bi imali ciklus od 4 povezana otoka). Pretpostavimo da plovi na linijama , , , .
Zato su preostala dva otoka i ukupno povezana s barem 4 linije (s ostalim otocima i eventualno međusobno). Zato je barem jedan od njih, recimo , povezan s otocima , , i s barem dvije linije.
Ako su obje s odredištima iz skupa , tada opet imamo ciklus od 4 povezana otoka , , i .
Ako je jedna od linija , a druga ili , opet imamo ciklus od 4 povezana otoka.
Pretpostavimo da poduzeće plovi na linijama i , a ne plovi na linijama i .
Ako još k tome plovi i na liniji , tada iz plovi prema jednom od otoka , , i (ukupno je 8 linija poduzeća ), te u svakom od tih slučajeva imamo ciklus od 4 povezana otoka.
Zato pretpostavimo da iz poduzeće plovi samo na linijama i . U tom slučaju iz poduzeća plovi na dvije linije prema otocima , , i . Istim zaključivanjem kao ranije zaključujemo da imamo ciklus od 4 povezana otoka, osim možda u slučaju kada su te dvije linije i . No, tada su ciklusom povezani otoci , , i .
