5. Zadatak

Pretpostavimo suprotno, tj. da ne postoji polje s tri plava brida. Tada svako polje ima barem dva crvena brida.

Sada brojimo parove oblika $(P,c)$, pri čemu je $P$ polje, a $c$ crveni brid koji omeđuje to polje. Prebrojit ćemo ih na dva različita načina.

Budući da je svako polje omeđeno s barem dva crvena brida, takvih parova ima barem $2n^2$. S druge strane, budući da svaki brid na rubu ploče ima samo jedno, a svaki brid u unutrašnjosti točno dva susjedna polja, broj parova $(P,c)$ možemo izraziti i kao $V+2U$, gdje je $V$ broj crvenih bridova na rubu ploče, a $U$ broj crvenih bridova u unutrašnjosti. Zaključujemo da vrijedi

$$2n^2\le 2U+V.$$

Nadalje, budući da ukupno imamo najviše $n^2$ crvenih bridova, vrijedi i

$$U+V\le n^2.$$

Zbrajanjem ovih dviju nejednakosti zaključujemo da mora biti $V=0$ i $U=n^2$. Dakle, u izvedenim nejednakostima vrijede jednakosti, pa svako polje ima točno dva crvena brida i svi se crveni bridovi nalaze u unutrašnjosti ploče.

Obojimo polja ploče šahovski, crno–bijelo. Primijetimo da svako bijelo polje sadrži točno dva crvena brida i da svaki crveni brid pripada točno jednom bijelom polju. To znači da crvenih bridova ima $2B$, gdje je $B$ broj bijelih polja. No to je kontradikcija jer crvenih bridova ima $n^2$, što je neparan broj.

Zaključujemo da je početna pretpostavka kriva, tj. da postoji polje s tri plava brida.