« Vrati se

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 njoj susjednim pločicama najviše je jedna u boji promatrane. 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?

Slični zadaci