5. Zadatak

Prvo rješenje.

a) Razlikujemo tri slučaja (uočimo da su to jedine mogućnosti):

1. Postoje tri retka koja sadrže po barem 2 označena polja. U tom slučaju biramo ta tri retka i preostanu najviše 3 označena polja pa odabiremo odgovarajuće stupce.
2. Postoji jedan redak koji sadrži barem 3 i jedan redak koji sadrži barem 2 označena polja. U tom slučaju biramo ta dva retka i preostanu najviše 4 označena polja pa biramo redak u kojem je jedno od tih polja i tri stupca u kojima su preostala polja.
3. Postoji redak koji sadrži barem 4 označena polja. U tom slučaju odabiremo taj redak i preostane najviše 5 označenih polja, a imamo na raspolaganju još dva retka i tri stupca pa vidimo da se i u ovom slučaju to može postići.

b) Jedno takvo označavanje dano je na slici:

Drugo rješenje.

a) Dokažimo da postoje tri retka koja sadrže barem šest označenih polja. Prema Dirichletovom principu postoje tri retka koja sadrže ukupno barem pet označenih polja. Pretpostavimo da su reci $R_1$, $R_2$ i $R_3$. Neka oni sadrže točno pet označenih polja (ako ih sadrže više, gotovi smo). Tada barem jedan od njih, neka je to $R_3$, sadrži najviše jedno označeno polje. Preostali reci $R_4$, $R_5$ i $R_6$ sadrže četiri označena polja, pa barem jedan od njih sadrži dva označena polja. Bez smanjenja općenitosti neka je to redak $R_6$. Tada reci $R_1$, $R_2$ i $R_6$ sadrže barem šest označenih polja. Odaberimo ta tri retka i tri stupca u kojima se nalaze preostala tri označena polja.

b) Primjer kao u prvom rješenju.