5. Zadatak
Ana je prekrila ploču dimenzija domino pločicama koje se međusobno ne preklapaju, a svaka od njih prekriva točno dva polja ploče. Branka želi obojiti te pločice tako da za svaku vrijedi: među pločicama koje su joj susjedne najviše su dvije boje promatrane pločice. Dvije pločice su susjedne ako prekrivaju polja koja imaju zajedničku stranicu.
Koliko je najmanje boja potrebno da bi Branka sigurno mogla obojiti pločice na takav način, neovisno o načinu na koji ih je Ana rasporedila?
Dokazat ćemo da su Branki dovoljne dvije boje.
Očito je da Branka ne može obojiti sve pločice jednom bojom: svaka pločica koja se ne nalazi na rubu ima barem četiri susjedne pločice (koje je diraju odozdo, odozgo, slijeva i zdesna) i koje su iste boje kao i promatrana, što nije dozvoljeno.
Dokažimo sada da, neovisno kako Ana postavi pločice, Branka može obojiti pločice dvjema bojama na ispravan način. Promotrimo sva crna polja ploče kada bismo je obojili crno-bijelo kao šahovsku ploču. Svaka pločica, neovisno o Aninom postavljanju, prekrit će točno jedno crno polje. Zato je, umjesto pločica, dovoljno svakom crnom polju ploče pridružiti jednu od dvije boje. Pločicu ćemo obojiti onom bojom koja je pridružena crnom polju koje prekriva.
To radimo kao na slici: poljima crne dijagonale pridružimo naizmjenično boje 1 i 2. Promotrimo proizvoljno crno polje. Bez smanjenja općenitosti možemo pretpostaviti da je tom polju pridružena boja 1. Pločica koja prekriva to polje bit će susjedna s nekim od osam crnih polja koja su od tog polja udaljena za dva polja. Među tim poljima imamo samo dva polja kojima je pridružena boja 1. Kako to vrijedi za proizvoljno polje, zaključujemo da će sve pločice biti susjedne s najviše dvije druge pločice iste boje.
