Tübitak Lise 1. Aşama 2011 Soru 32

[ERhan ERdoğan]

Başlangıçta bir öbekte $n$ taş bulunuyor. İki oyuncu sırayla hamle yapıyorlar ve her hamlede sırası gelen oyuncu istediği bir $i\geqslant 0$ tam sayısı için öbekteki taşlardan $2^{i}$ tanesinin alıyor. Son taşı alan oyuncu oyunu kazanıyor. Oyun $n=1000,2000,2011,3000,4000$ değerlerinin her biri için birer kez oynanırsa, bu oyunlardan kaçını oyuna başlayan oyuncu kazanmayı garantileyebilir ?

$
\textbf{a)}\ 4
\qquad\textbf{b)}\ 3
\qquad\textbf{c)}\ 2
\qquad\textbf{d)}\ 1
\qquad\textbf{e)}\ \text{Hiçbiri}
$

[ERhan ERdoğan]

(Barış DEMİR)

$n=3k$ için oyunu daima ikinci oyuncu kazanır.

$i\geq0$ için birinci oyuncu $2^i$ taş alsın, geriye $3k-2^i$ taş kalır.

$3k-2^i \equiv 1\pmod 3$ veya $3k-2^i \equiv 2\pmod 3$ 

Eğer, $3k-2^i \equiv 1\pmod 3$ ise, ikinci oyuncu $2^k \equiv 1\pmod 3$ olacak biçimde taş alarak birinci oyuncuya $3k-2^i -2^k \equiv 0\pmod 3$
olacak şekilde taş bırakır.Yani tekrar 3 ün katı olan bir taş miktarı kalır.

Eğer,  $3k-2^i \equiv 2\pmod 3$ ise, 2.oyuncu $2^k \equiv 2\pmod 3$ olacak biçimde taş alarak birinci oyuncuya $3k-2^i -2^k \equiv 0\pmod 3$
olacak şekilde taş bırakır.Yani tekrar 3 ün katı olan bir taş miktarı kalır.

birinci oyuncu ne yaparsa yapsın ikinci oyuncu mutlaka ona 3 ün katı olacak biçimde taş bırakacaktır. 1.oyuncu en iyi ihtimalle bu durumu 3 taşa kadar sürdürecektir.3 taş kalınca da ya $2^0$ alacak ve ikinci oyuncu $2^1$ alarak kazanacak ya da tam tersi $2^1$ alacak ve ikinci oyuncu $2^0$ alarak kazanacaktır.

$n=3k+1$ ve $n=3k+2$ için de oyunu daima birinci oyuncu $n=3k$ da ikinci oyuncunun uyguladığı taktiği uygulayarak kazanır.

O halde verilen sayılardan $1000, 2000, 2011, 4000$ için oyunu birinci oyunu kazanır.