5. Zadatak
Odredi najveći prirodni broj za koji se svako polje pravokutne ploče može obojiti u jednu od dvije boje tako da za svaki izbor dvaju redaka i dvaju stupaca vrijedi da četiri polja u presjecima tih redaka i stupaca nisu sva obojana istom bojom.
Neka je . Obojimo ploču na sljedeći način:
Vidimo da ne možemo odabrati dva retka i dva stupca tako da su u njihovim presjecima sva polja obojana istom bojom.
Dokažimo da se, za svako bojanje ploče mogu naći dva retka i dva stupca takva da su četiri polja u presjecima tih redaka i stupaca obojana istom bojom.
Promotrimo prvi redak. Barem tri polja u tom retku moraju biti obojana istom bojom, recimo da je to crvena. Uočimo tri stupca koja u prvom retku imaju crveno polje. Možemo pretpostaviti da su to prva tri stupca.
Ako u nekom preostalom retku tih stupaca imamo dva crvena polja, dobili smo dva retka i dva stupca takva da su četiri polja u presjecima tih redaka i stupaca obojana istom bojom. Na primjer:
Dakle, pretpostavimo da u svakom preostalom retku tog stupca moramo imati najviše jedno crveno polje. No tada u svim tim recima imamo po dva plava polja.
Ona mogu biti ili u prva dva stupca ili u prvom i trećem ili u drugom i trećem.
Primjer:
No, to znači da se jedna takva „pozicija“ mora ponoviti pa smo opet dobili dva retka i dva stupca takva da su četiri polja u presjecima tih redaka i stupaca obojana istom bojom, u ovom slučaju plavom bojom.
U ploči , gdje je , uvijek možemo odabrati dio te ploče za koji smo pokazali da uvijek možemo naći četiri polja u presjecima tih redaka i stupaca obojana istom bojom.
Zato je najveći za koji se svako polje pravokutne ploče može obojiti u jednu od dvije boje tako da za svaki izbor dvaju redaka i dvaju stupaca vrijedi da četiri polja u presjecima tih redaka i stupaca nisu sva obojana istom bojom.