5. Zadatak

Dva igrača, $A$ i $B$ igraju sljedeću igru: $A$ i $B$ zapisuju naizmjenično po jednu znamenku sve dok ne napišu šesteroznamenkasti broj, pri čemu se niti jedna znamenka ne smije ponoviti. Prva znamenka mora biti različita od 0. Igrač $A$ igra prvi, a znamenke se pišu redom s lijeva na desno. Igrač $A$ pobjeđuje ako je napisani šesteroznamenkasti broj djeljiv s 2, 3 ili 5, a u suprotnom pobjeđuje igrač $B$ . Dokaži da igrač $A$ ima strategiju za pobjedu, tj. može pobijediti neovisno o igri igrača $B$ .

Rješenje

Neka su $a_1$ , $a_2$ , $a_3$ znamenke koje izabire $A$ , a $b_1$ , $b_2$ , $b_3$ znamenke koje izabire $B$ . Dobiveni broj je $x=\overline{a_1b_1a_2b_2a_3b_3}$ . Neka je $M=\{0,2,4,5,6,8\}$ i $N=\{1,3,7,9\}$ . Ako je $b_3\in M$ , broj $x$ je djeljiv s 2 ili 5. Stoga $B$ ne smije svoju zadnju znamenku odabrati iz skupa $M$ . Zato $A$ bira svoje prve dvije znamenke iz $N$ prisiljavajući time igrača $B$ da svoje prve dvije znamenke bira iz $M$ (u suprotnom bi $A$ mogao potrošiti zadnju znamenku iz $N$ prije zadnjeg poteza igrača $B$ , pa bi bilo $b_3\in M$ i $A$ pobjeđuje). Igrač $A$ mora postići da broj $x$ bude djeljiv s 3. Neka je $a_1=3$ , $a_2=9$ . Tada je $b_3\equiv1\pmod3$ jer iz skupa $N$ preostaju znamenke 1 i 7. Broj $x$ bit će djeljiv s 3 ako je $a_1+b_1+a_2+b_2+a_3+b_3$ djeljivo s 3. Ovisno o odabiru $b_1$ i $b_2$ , imamo 3 mogućnosti:

(1) $b_1+b_2\equiv0\pmod3$ . Tada je $a_1+b_1+a_2+b_2+a_3+b_3\equiv a_3+1\pmod3$ . Igrač $A$ može odabrati za $a_3$ jednu od znamenaka 2, 5 ili 8 (barem jedna od njih je još neiskorištena).

(2) $b_1+b_2\equiv1\pmod3$ . Tada je $a_1+b_1+a+b_2+a_3+b_3\equiv a_3+2\pmod3$ . Sada $A$ može odabrati $a_3=1$ .

(3) $b_1+b_2\equiv2\pmod3$ . Tada je $a_1+b_1+a+b_2+a_3+b_3\equiv a_3\pmod3$ . U ovom slučaju $A$ bira $a_3=0$ ili $a_3=6$ . Barem jedan on njih je na raspolaganju, jer da je $B$ odabrao oba, bilo bi $b_1+b_2\equiv0\pmod3$ . U svakom slučaju suma znamenaka bit će djeljiva s 3, pa će i $x$ biti djeljiv s 3, a igrač $A$ pobjednik.