5. Zadatak

Pretpostavimo suprotno, tj. da postoji raspored bombona za koji sva djeca nikad neće imati jednako mnogo bombona, te da će zato ova igra trajati proizvoljno mnogo koraka.

Nazovimo prvi dio koraka (dodjela jednog bombona djeci s neparno mnogo bombona) priprema, a drugi dio koraka (raspodjela polovine bombona desnim susjedima) distribucija.

Označimo s $2x_1,2x_2,\ldots,2x_n$ količine bombona djece redom u krugu nakon prve izvršene pripreme, a prije nego se izvršila prva distribucija. Neka je $2x_{\max}$ najveća količina bombona među tim vrijednostima.

Lako je vidjeti da nakon jedne izvršene distribucije nijedno dijete nema više od $2x_{\max}$ bombona budući da svako dijete nakon distribucije ima $x_i+x_j$ bombona (za neke indekse $i,j\in\{1,\ldots,n\}$), a oba broja $x_i$, $x_j$ su manja od ili jednaka $x_{\max}$. Također, ni nakon pripreme koja uslijedi nakon te distribucije nijedno dijete neće imati više od $2x_{\max}$ bombona: ako je nakon distribucije imalo parno mnogo bombona, nakon pripreme neće imati više, a ako je nakon distribucije imalo neparno mnogo bombona, taj broj je strogo manji od $2x_{\max}$ (jer je neparan), pa ni uvećan za $1$ neće biti veći od te vrijednosti.

Ponavljajući ovaj argument, vidimo da najveća količina bombona koja se može naći kod nekog djeteta u svakom trenutku sigurno nije veća od $2x_{\max}$.

Sada možemo zaključiti da postoji trenutak nakon kojeg se u pripremama više nikad ne dodijeli nijedan bombon. U suprotnom ukupna količina bombona među djecom bi neograničeno rasla i postojao bi trenutak u kojem bi neko dijete imalo više od $2x_{\max}$ bombona, što nije moguće.

Promotrimo prvi trenutak nakon kojeg se ni u jednoj pripremi više ne dijele bomboni. To znači da su u svakom sljedećem koraku sve količine bombona kod djece parni brojevi. Neka su $2y_1,\ldots,2y_n$ količine bombona djece redom u krugu u bilo kojem takvom koraku. Neka je $K$ suma kvadrata količine bombona kod svakog djeteta:

$$K=(2y_1)^2+(2y_2)^2+\cdots+(2y_n)^2.$$

Očito je $K$ nenegativan cijeli broj. Također, kako je kod svakog djeteta najviše $2x_{\max}$ bombona, vrijedi $K\le n\cdot(2x_{\max})^2$. Dakle, $K$ je cijeli broj koji može poprimiti konačno mnogo vrijednosti.

Pogledajmo kako se vrijednost $K$ mijenja nakon jednog koraka. Kako se u pripremi više ništa ne dogodi, količine bombona kod djece redom u krugu nakon distribucije su $y_n+y_1$, $y_1+y_2$, $\ldots$, $y_{n-2}+y_{n-1}$, $y_{n-1}+y_n$. Razlika suma kvadrata vrijednosti prije i poslije tog koraka je

$$\begin{aligned} &(2y_1)^2+(2y_2)^2+\cdots+(2y_n)^2\\ &\quad-\bigl[(y_n+y_1)^2+(y_1+y_2)^2+\cdots+(y_{n-1}+y_n)^2\bigr]\\ &=2(y_1^2+y_2^2+\cdots+y_n^2)-2(y_ny_1+y_1y_2+\cdots+y_{n-1}y_n)\\ &=(y_n-y_1)^2+(y_1-y_2)^2+\cdots+(y_{n-1}-y_n)^2. \end{aligned}$$

Dakle, gornja razlika je nenegativan cijeli broj. Ona je jednaka nuli samo u slučaju kada su svi brojevi $y_1,\ldots,y_n$ jednaki, što znači da su sve količine bombona jednake, što je u kontradikciji s pretpostavkom. Dakle, ta razlika je prirodan broj. No, tada zaključujemo da se svakim korakom suma kvadrata količine bombona smanji za neki prirodan broj. Kako suma kvadrata količine bombona može postići samo konačno mnogo vrijednosti, to se može ponavljati samo konačno mnogo puta.

Time smo dobili kontradikciju s pretpostavkom na početku rješenja pa postoji trenutak u kojem će sva djeca imati jednak broj bombona.