3. Zadatak
a) Dokažite da se ploča dimenzija može obojiti u 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.
b) Dokažite da gore navedeno svojstvo ne vrijedi za ploču dimenzija .
Rješenje
a) Jedno moguće bojanje prikazano je na slici:
b) Pretpostavimo suprotno, tj. da je ploča dimenzija obojana bijelom i crnom bojom tako da je uvjet ispunjen.
U prvom retku jednom su bojom (recimo crnom) obojana barem tri polja. Uočimo stupce u kojima je prvo polje crno:
Ako bi u drugom retku bila sva tri polja bijela, dalje bi bilo nemoguće popuniti tablicu.
Zapravo, u svakom od preostala četiri retka tih triju stupaca moraju biti točno dva bijela polja. Naime, ako bi bila dva (ili tri) crna polja, uvjet ne bi bio ispunjen.
No, to nije moguće jer takvih mogućnosti imamo samo tri (a ponavljanja ne smije biti).