5. Zadatak

Ana je prekrila ploču dimenzija $2020 \times 2020$ 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 je jedna 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 tri boje.

Prvo dokažimo da Branki nisu dovoljne dvije boje (a time ni manje). Naći ćemo primjer Aninog prekrivanja u kojem Branka nikako ne može obojiti pločice dvjema bojama.

Primjer prekrivanja gornjeg lijevog dijela ploče domino pločicama A, B, C, D, E i F

Neka Ana prekrije gornji lijevi $3 \times 4$ dio ploče kao na slici, a preostali dio postavljajući pločice horizontalno. Imenujmo pločice kao na slici. Pločice $A$ , $B$ i $C$ su sve u parovima susjedne. Kako imamo dvije boje (1 i 2), po Dirichletovom principu barem dvije pločice su obojene istom bojom (bez smanjenja općenitosti bojom 1). Ako su to pločice $A$ i $B$ , tada sve njima susjedne pločice moraju biti obojene bojom 2. Odnosno, pločice $C$ , $E$ i $F$ su obojene bojom 2, što znači da $C$ ima dvije susjedne istobojne pločice.

S druge strane, ako je $C$ iste boje kao neka od pločica $A$ ili $B$ , tada sve ostale susjedne pločice pločici $C$ moraju biti boje 2. Tada su $D$ , $E$ i $F$ obojene bojom 2, što znači da $D$ ima dvije susjedne istobojne pločice.

U oba slučaja dolazimo do kontradikcije, stoga su potrebne barem tri boje.

Dokažimo sada da, neovisno kako Ana postavi pločice, Branka može obojiti pločice trima bojama na ispravan način. Promotrimo sva crna polja $2020 \times 2020$ 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 $2020 \times 2020$ pridružiti jednu od tri boje. Pločicu ćemo obojiti onom bojom koja je pridružena crnom polju koje prekriva.

Dodatno, za konstrukciju bojenja, podijelimo ploču $2020 \times 2020$ na $2 \times 2$ blokove. Obojiti jedan blok znači pridružiti njegovim crnim poljima (dakle poljima u gornjem lijevom i donjem desnom kutu) istu boju. Blokove bojimo izmjenjujući redom sve tri boje, kao na slici.

Shema pridruživanja boja 1, 2 i 3 crnim poljima ploče

Dvije pločice mogu biti susjedne samo ako im je udaljenost crnih polja koja prekrivaju najviše 2. Stoga promotrimo dva polja u istom $2 \times 2$ bloku kojima je pridružena ista boja (bez smanjenja općenitosti boja 1). Sa slike vidimo da polja kojima je pridružena boja 1 imaju u svojoj blizini najviše jedno polje kojem je pridružena ista boja. Kako to vrijedi za proizvoljno polje s pridruženom proizvoljnom bojom, zaključujemo da će sve pločice biti susjedne s najviše jednom pločicom iste boje.