5. Zadatak

Dva igrača naizmjence zapisuju po jednu znamenku, redom slijeva nadesno. Igrač gubi ako je nakon njegovog poteza napisan niz znamenaka $a_1,a_2,\ldots,a_n$ za koji postoji prirodni broj $k$ takav da je broj $\overline{a_ka_{k+1}\ldots a_n}$ djeljiv s $11$ . Koji igrač može pobijediti neovisno o igri protivnika?

Rješenje

Pokazat ćemo da igrač koji je drugi na potezu može pobijediti neovisno o igri igrača koji je prvi na potezu. Očito nijedan igrač neće napisati nulu ni u kojem koraku.

Uočimo da je $10^r\equiv(-1)^r\pmod{11}$ , pa vrijedi sljedeći kriterij za djeljivost s $11$ :

\overline{a_ka_{k+1}\ldots a_n}\equiv a_n-a_{n-1}+a_{n-2}-\cdots+(-1)^{n-k}a_k\pmod{11}.

Označimo s $N_k$ ostatak broja $\overline{a_ka_{k+1}\ldots a_n}$ pri dijeljenju s $11$ , za $k=1,\ldots,n$ . Ako su u $n$ -tom potezu brojevi $N_1,\ldots,N_n$ svi različiti, onda u sljedećem potezu dobivamo brojeve

a_{n+1}-N_1,\ldots,a_{n+1}-N_n,a_{n+1}\pmod{11},

koji su također svi različiti jer je $a_{n+1}\ne0$ . Induktivno zaključujemo da su u svakom potezu igre (za $n\le10$ ) brojevi $N_1,\ldots,N_n$ različiti. Također, zbog načina na koji se brojevi $N_1,\ldots,N_n$ transformiraju u svakom potezu, zaključujemo da postoji najviše $n+1$ znamenki čijim zapisivanjem igrač na potezu gubi.

Pretpostavimo da igra traje barem devet poteza. Drugi igrač gubi ako i samo ako je u devetom potezu skup $\{N_1,N_2,\ldots,N_9\}$ jednak skupu $\{1,2,\ldots,9\}$ , tj. drugi igrač pobjeđuje ako i samo ako se među brojevima $N_1,N_2,\ldots,N_9$ pojavljuje broj $10$ .

Ako u osmom potezu u skupu $\{N_1,\ldots,N_8\}$ nedostaju dva broja od $1$ do $10$ koji nisu uzastopni, onda bez obzira na odabir prvog igrača u devetom potezu jedan od brojeva $N_1,\ldots,N_9$ mora biti $10$ . Naime, ako prvi igrač odabere broj $X$ , onda postoji $k$ takav da je u osmom potezu $N_k=X+1$ i u devetom potezu dobivamo

N_k\equiv X-(X+1)\equiv-1\equiv10\pmod{11}.

Pokažimo da drugi igrač može osigurati da u osmom potezu među brojevima $N_1,\ldots,N_8$ nema dva uzastopna broja. Svakako drugi igrač može osigurati da igra traje barem sedam poteza. Neka u sedmom potezu vrijedi

\{N_1,\ldots,N_7\}=\{1,2,\ldots,10\}\setminus\{X,Y,Z\}.

Ako među brojevima $X,Y,Z$ nema uzastopnih, drugi igrač može odabrati bilo koji od njih. Ako je $Y=X+1$ , drugi igrač može napisati jedan od brojeva $X$ ili $X+1$ tako da u osmom potezu među brojevima $N_1,\ldots,N_8$ nema dva uzastopna broja. Naime, ako je $Z=X-1$ , drugi igrač napiše $X$ , a ako je $Z\ne X-1$ , onda drugi igrač napiše $X+1$ .