5. Zadatak

Prvo rješenje:

Odgovor je ne.

Dvije od 16 boja možemo izabrati na $\binom{16}{2}=120$ načina.

Da bi uvjet zadatka bio zadovoljen, za svaki par boja mora postojati par susjednih polja, odnosno stranica koja povezuje dva susjedna polja.

Prebrojimo koliko ima stranica (bridova) koje dijele dva susjedna polja. U svakom od 8 redaka ima 7 takvih vertikalnih stranica, te u svakom od 8 stupaca ima 7 takvih horizontalnih stranica, što je ukupno $112$.

Prema tome, ne može postojati po jedna stranica za svaki par boja.

Drugo rješenje:

Pretpostavimo da je takvo bojanje moguće.

Jedno polje ima najviše 4 susjeda. Za fiksnu boju $b$ trebamo barem 4 polja u toj boji kako bismo imali 15 parova oblika $(b,c)$ gdje je $c$ neka druga boja.

Dakle, u svakoj boji moramo imati barem 4 polja. No broj polja je 64 i $16\cdot4=64$, pa mora vrijediti da u svakoj boji imamo točno 4 polja.

Promotrimo boju kojom je obojano polje u nekom uglu, primjerice gornjem lijevom. U toj boji postoje još 3 polja, koja imaju najviše po 4 susjeda svako, a polje u uglu ima 2 susjeda. Prema tome, polja u toj boji imaju najviše 14 susjeda. Ta boja ne može biti susjedna sa svih 15 preostalih boja, što je kontradikcija s pretpostavkom.

Dakle, odgovor je ne.