5. Zadatak
Dana je ploča dimenzija . U gornjem lijevom polju ploče nalazi se muha. Muha se može kretati na dva načina - korakom i letom. Korak je pomak na polje neposredno ispod ili desno od polja na kojem se trenutno nalazi. Letom muha prelazi sa zadnjeg (krajnjeg desnog) polja na prvo (krajnje lijevo) polje u istom retku ili sa zadnjeg (donjeg) polja na prvo (gornje) polje u istom stupcu.
Koji je najmanji broj letova koje muha mora napraviti da bi posjetila svako polje ploče točno jednom?
Prvo rješenje.
Odgovor je letova.
Proglasimo crnim polja ploče koja leže na dijagonali koja spaja polje u gornjem desnom kutu i polje u donjem lijevom kutu. Tih polja je ukupno .
Primijetimo da muha ne može doći od jednog crnog polja ploče do drugog bez da između izvede barem jedan let. Naime, na kojem se god crnom polju ploče nalazi, polja ispod nje su joj nedostupna bez letova jer koracima ne može ići ulijevo, a crna polja iznad nje su joj nedostupna jer koracima ne može ići prema gore.
Nakon što muha posjeti prvo crno polje, kako bi posjetila preostalih polja mora izvesti još barem letova. Dakle, ne postoji šetnja po svim poljima ploče s manje od letova.
Da zaista jest najmanji broj letova, dokazujemo konstrukcijom jedne takve šetnje. Neka muha izmjenjuje poteza (koraka ili letova) udesno, pa jedan potez prema dolje. Ako se u nekom trenutku nalazi na desnom rubu ploče kada treba napraviti potez udesno, tada će muha napraviti let na prvo polje tog retka. Neka to ponovi puta, bez da deseti put napravi korak prema dolje.
Nakon svakih poteza udesno muha će posjetiti sva polja tog retka točno jednom. Jednim korakom prema dolje prvi put će posjetiti neko polje novog retka. Na taj način posjetit će sva polja točno jednom. Ukupan broj letova je zaista : izvest će let točno jednom u svakom retku osim prvom.
Drugo rješenje.
Kao u prvom rješenju, tvrdimo da je najmanji mogući broj letova jednak .
Svakom polju ploče koje se nalazi u -tom retku i -tom stupcu () pridružimo vrijednost .
Primijetimo da svakim korakom muha posjećuje polje kojem je vrijednost veća za od vrijednosti prošlog polja, a letom posjećuje polje kojem je vrijednost manja za .
Neka je broj letova koje je muha izvela u jednoj šetnji po svim poljima ploče. To znači da je puta izvela korak i time uvećala vrijednost prethodno posjećenog polja za , a puta smanjila tu vrijednost za .
Budući da je muha krenula s polja vrijednosti , završila na polju kojem je vrijednost najviše , mora vrijediti
odnosno .
Najmanji prirodni koji zadovoljava gornju nejednakost je , što znači da broj letova ne smije biti manji od .
Šetnju s letova konstruiramo kao u prvom rješenju.