Vrijeme: 15:06

Invarijante: Žeton u ravnini - RJEŠENJE

Promatrajmo najveći zajedničkii djelitelj brojeva a i b u paru koordinata (a,b). Potezom prvog tipa udvostručujemo neku od koordinata što može dovesti do udvostručenja najvećeg zajedničkog djelitelja, ili ga ostavlja jednakim. Potezom drugog tipa oduzimamo manji član od većega čime se također ne mijenja najveći zajednički djelitelj. Dakle, ako su (a,b) brojevi prije poteza, a (a',b') nakon poteza, vrijedi M(a',b')=M(a,b) ili M(a',b')=2M(a,b). Kako je početni najveći zajednički djelitelj 1, vidimo da će u svakom trenutku najveći zajednički djelitelj biti neka potencija broja 2. Zato su jedine potencijalno dostižne točke nužno oblika (a \cdot 2^n, b \cdot 2^n), pri čemu je n \in \mathbb{N}_0 i M(a,b)=1.

Pokažimo da je zaista svaka takva točka dostižna. Kako je M(a,b)=1, barem jedan od tih brojeva je neparan. Bez smanjenja općenitosti, neka je to a. Udvostručimo prvu koordinatu m puta tako da je 2^m > a \cdot 2^n, a drugu koordinatu točno n puta. Došli smo do točke (2^m, 2^n). Sada oduzmimo 2^{m-n} - a puta drugu koordinatu od prve. Time dolazimo do točke (a \cdot 2^n, 2^n). Neka je sada k \in \mathbb{N} takav da je 2^k>b. Budući da je a neparan, brojevi 2^k, \, 2^{k+1}, ..., 2^{k+a-2} čine reducirani sustav ostataka pri dijeljenju s a, odnosno među tih a-1 brojeva su svi mogući ostatci pri dijeljenju s a osim 0. Tada postoji l takav da je k \leq l \leq k+a-2 i 2^l \equiv b \pmod{a}. Drugim riječima, postoji prirodan broj c takav da je 2^l = b + ca. Udvostručimo sada drugu koordinatu l puta - time dolazimo do točke (a \cdot 2^n, 2^n \cdot 2^l) = (a \cdot 2^n, b \cdot 2^n + c \cdot a \cdot 2^n). Preostaje c puta oduzeti prvu koordinatu od druge i dolazimo do željene točke.go

-------------------------------

NAPOMENA: Drugi dio rješenja nije ispravan, jer brojevi 2^k, \, 2^{k+1}, ..., 2^{k+a-2} ne moraju činiti reducirani sustav ostataka pri dijeljenju s a (recimo za a=7). Zaključak stoga nije ispravan, recimo kontraprimjer je (3,7) koji ne može biti postignut.