5. Zadatak

Dana je ploča dimenzija $2020\times2022$ . Za dva polja te ploče kažemo da su susjedna ako imaju zajedničku stranicu ili se nalaze na početku i kraju istog retka ili stupca. Dakle, svako polje ima točno četiri susjedna polja.

Viktor u svakom koraku bira jedno polje ploče i na ploču postavlja pet žetona: po jedan na odabrano polje i na svako polje susjedno odabranom. Nakon konačnog broja takvih koraka, na svakom polju nalazi se točno $d$ žetona.

Odredi najmanji mogući $d$ .

Reći ćemo da je na nekom polju izveden potez ako je Viktor izabrao to polje ploče, te stavio žeton na to polje i četiri njemu susjedna polja.

Dokazat ćemo da je najmanji mogući $d$ jednak $5$ . Taj se broj žetona može postići tako što će Viktor izvesti potez na svakom polju točno jednom. Time smo na svako polje ploče jednom stavili žeton kada smo izveli potez na tom polju, te još četiri puta kada smo izveli potez na nekom njegovom susjedu.

Dokažimo sada da je nužno $d\geq5$ . Pretpostavimo da nakon konačno mnogo poteza se na svakom polju ploče nalazi točno $d$ žetona.

Obojimo ploču u $5$ boja tako da svaki peti redak obojimo u istu boju. Označimo boje prvih pet redaka s $1,2,3,4,5$ , redom. Za indeks $i\in\{1,2,3,4,5\}$ , označimo $x_i$ ukupan broj poteza izvedenih na svim poljima boje $i$ .

U svakom retku nalazi se $2022$ polja, a bojom $i$ obojeno je $404$ redaka. Zato je ukupan broj žetona koji se nalaze u svim poljima obojenih bojom $i$ jednak $d\cdot2022\cdot404$ . S druge strane, na polja obojena bojom $i$ postavili bismo $3$ žetona svakim potezom izvedenim na polju obojenom bojom $i$ , te po jedan žeton svakim potezom izvedenim na polju obojenom bojom $i-1$ i $i+1$ . Zato zaključujemo da za svaki $i$ vrijedi jednakost

x_{i-1}+3x_i+x_{i+1}=d\cdot2022\cdot404,

gdje smo poistovjetili $x_0=x_5$ , te $x_6=x_1$ . Prosumirajmo svih $5$ dobivenih jednakosti, i podijelimo dobiveno s $5$ . Dobivamo

x_1+x_2+x_3+x_4+x_5=d\cdot2022\cdot404.

Sada oduzmimo zadnju jednakost s prethodno $5$ dobivenih. Dobivamo sustav $5$ jednadžbi s $5$ nepoznanica:

\begin{aligned} x_4-2x_1+x_3&=0,\\ x_5-2x_2+x_4&=0,\\ x_1-2x_3+x_5&=0,\\ x_2-2x_4+x_1&=0,\\ x_3-2x_5+x_2&=0. \end{aligned}

Dokažimo da je jedino rješenje ovog sustava u nenegativnim cijelim brojevima kada su svi brojevi $x_i$ međusobno jednaki. Bez smanjenja općenitosti, neka je $x_1$ najveći među njima. Tada iz prve jednakosti sustava dobivamo

x_4+x_3=2x_1\geq x_3+x_4,

gdje jednakost vrijedi samo ako je $x_1=x_3=x_4$ . Sada iz treće jednakosti sustava dobivamo

x_5=2x_3-x_1=x_1,

a iz četvrte

x_2=2x_4-x_1=x_1.

Time smo dobili da su svi $x_i$ , za $i\in\{1,2,3,4,5\}$ , međusobno jednaki. Za njihov zbroj vrijedi

5x_1=x_1+x_2+x_3+x_4+x_5=d\cdot2022\cdot404.

Kako je lijeva strana jednakosti djeljiva s $5$ , mora biti i desna. To je moguće tek ako je $5\mid d$ , a kako je $d$ prirodan, posebno vrijedi $d\geq5$ .

Dakle, najmanji mogući takav $d$ je jednak $5$ .