5. Zadatak

Ukrug je napisano 299 nula i jedna jedinica. Dozvoljeni su sljedeći potezi:

svakom broju istovremeno oduzeti njemu oba susjedna broja;
odabrati dva broja između kojih se nalaze točno dva broja te ih oba uvećati ili oba umanjiti za 1.

Može li se konačnim nizom dozvoljenih poteza postići da ukrug budu napisane

(a) dvije uzastopne jedinice i 298 nula?

(b) tri uzastopne jedinice i 297 nula?

Analizirat ćemo što se događa s određenim zbrojevima brojeva pri primjeni poteza. Označimo s $a_k$ brojeve koji su zapisani u nekom trenutku, i to tako da je $a_1$ na onom mjestu u krugu na kojem se na početku nalazi jedinica, te $a_2,\ldots,a_{300}$ označavaju redom brojeve u smjeru kazaljke na satu. Nakon primjene prvog poteza dobivamo brojeve

\begin{aligned} b_1&=a_1-a_{300}-a_2,\\ b_k&=a_k-a_{k-1}-a_{k+1}, \qquad k=2,\ldots,299,\\ b_{300}&=a_{300}-a_{299}-a_1. \end{aligned}

(a) Promotrimo kako se mijenja zbroj svih napisanih brojeva kad primjenjujemo dozvoljene poteze. Ako ukupni zbroj brojeva $a_k$ iznosi

S=a_1+a_2+\ldots+a_{300},

onda zbroj brojeva $b_k$ iznosi

a_1-a_{300}-a_2+a_2-a_1-a_3+\ldots+a_{300}-a_{299}-a_1=-S

jer svaki broj $a_k$ jednom pribrojimo i dvaput oduzmemo.

Nakon primjene drugog poteza zbroj svih brojeva će biti $S+2$ ili $S-2$ . Zaključujemo da se primjenom dozvoljenih poteza ne može promijeniti parnost zbroja svih brojeva. Budući da je na početku zbroj svih brojeva 1 (neparan broj), nije moguće postići da budu zapisane dvije jedinice i 298 nula jer bi tada zbroj svih brojeva bio 2 (paran broj).

(b) Promotrimo kako se mijenja alternirajući zbroj napisanih brojeva. Ako alternirajući zbroj brojeva $a_k$ iznosi

S'=a_1-a_2+a_3-\ldots+a_{299}-a_{300},

onda će nakon primjene prvog poteza alternirajući zbroj svih brojeva $b_k$ biti

a_1-a_{300}-a_2-a_2+a_1+a_3+\ldots-a_{300}+a_{299}+a_1=3S',

dok će nakon primjene drugog poteza alternirajući zbroj svih napisanih brojeva ostati $S'$ .

Pretpostavimo da je moguće postići da budu napisane tri uzastopne jedinice i 297 nula. Na početku je alternirajući zbroj svih brojeva 1, a kad bi bile zapisane tri uzastopne jedinice i 297 nula alternirajući zbroj svih brojeva bi iznosio ili 1 ili $-1$ , ovisno o tome na kojim mjestima se nalaze jedinice. Budući da se dozvoljenim potezima alternirajući zbroj ili utrostručuje ili ostaje isti, zaključujemo da tri jedinice moraju biti na mjestima tako da je alternirajući zbroj 1 te da ne smijemo koristiti prvi potez.

Promotrimo zbroj brojeva na mjestima $3,6,\ldots,300$ , tj.

S_0=a_3+a_6+\ldots+a_{300}.

Na početku je taj zbroj 0, a kad bi bile zapisane tri uzastopne jedinice i 297 nula taj bi zbroj iznosio 1. No, primjenom samo drugog poteza parnost tog zbroja se ne mijenja jer ili ne mijenjamo nijedan od brojeva $a_3,a_6,\ldots,a_{300}$ ili mijenjamo točno dva broja za 1. Kako 0 i 1 nisu iste parnosti, to pokazuje da dozvoljenim potezima nije moguće postići da budu napisane tri uzastopne jedinice i 297 nula.