5. Zadatak
Na ploču dimenzija treba rasporediti određeni broj žetona tako da se na nekim poljima nalazi po jedan žeton, a neka su polja prazna. Za raspored žetona kažemo da je siguran ako se svaki žeton nalazi na polju kojemu su sva susjedna polja prazna (dva polja smatraju se susjednima ako imaju zajedničku stranicu). Za koji najmanji prirodan broj postoji siguran raspored žetona takav da se na ploču ne može dodati nijedan žeton, a da raspored i dalje bude siguran?
Prvo rješenje.
Odgovor je .
Primijetimo da za svaki postavljeni žeton na ploči postoji najviše polja na koja se ne može postaviti žeton. To su polje na kojem je žeton, i sva njemu susjedna polja (kojih je najmanje ).
Pretpostavimo da je moguće postići željeni raspored s žetona. Tada postoji ukupno najviše polja na koje se ne može dodati žeton. Kako na ploči imamo polja, ostaje barem jedno polje na koje se može dodati žeton, dakle mora vrijediti .
Jedan siguran raspored s četiri žetona dan je na slici.
Drugo rješenje.
Odgovor je .
Promotrimo polje koje se nalazi u gornjem lijevom kutu ploče te njemu susjedna polja (ispod i desno od njega). Na jednom od ta tri polja mora se nalaziti žeton, u suprotnom bi se mogao dodati žeton na kutno polje.
Isto možemo zaključiti i za preostala kutna polja ploče.
Kako među kutnim poljima i njima susjednim poljima nema preklapanja, potrebno nam je barem žetona za siguran raspored.
Primjer sigurnog rasporeda s četiri žetona je isti kao u prvom rješenju.