5. Zadatak

Tvrdimo da je traženi najmanji broj bubamara jednak $2016^2+1$.

Pokažimo najprije da postoji početna pozicija i kretanje za $2016^2$ bubamara tako da se u niti jednom trenutku dvije bubamare neće naći na istom polju. Bubamare smjestimo u donji lijevi $2016\times2016$ kvadrat dane ploče i neka se sve kreću jednako: gore, desno, dolje, lijevo, gore, desno, … Vidimo da u prva $4$ koraka nijedne dvije neće doći na isto polje, a kako se nakon $4$ koraka vraćamo na početak, vidimo da se nikada neće dvije bubamare naći na istom polju.

Pokažimo sada da ukoliko se na ploči nalazi $2016^2+1$ bubamara, neovisno o početnom rasporedu i pomacima, neke dvije će se u nekom trenutku naći na istom polju.

Obojimo polja ploče u $4$ boje, $A$, $B$, $C$ i $D$, na način da polja u neparnim retcima bojamo naizmjence bojama $A$ i $B$, a ona u parnim retcima naizmjence bojama $C$ i $D$. Za polje obojano bojom $A$ kratko kažemo $A$-polje.

U rješenju su nam ključne sljedeće dvije činjenice. Bubamara koja se nalazi na $B$-polju ili $C$-polju nakon jednog koraka prelazi na $A$-polje ili $D$-polje. Također, bubamara koja se nalazi na $A$-polju nakon dva koraka prelazi na $D$-polje.

Na ploči se nalazi $2016^2+1$ bubamara pa možemo pretpostaviti da se njih barem $1008\cdot2016+1$ nalazi na $A$-polju ili $D$-polju. U suprotnom ih je barem $1008\cdot2016+1$ na $B$-polju ili $C$-polju, pa nakon jednog koraka postižemo da je veći broj bubamara na $A$-poljima i $D$-poljima. Budući da broj $D$-polja iznosi $1008^2$, na $A$-poljima se nalazi barem $1008^2+1$ bubamara.

Sve bubamare koje se nalaze na $A$-poljima će nakon dva koraka prijeći na $D$-polja, što znači da se na $1008^2$ $D$-polja nalazi barem $1008^2+1$ bubamara, tj. neke dvije bubamare će se naći na istom polju.