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

[geo]

Ali, $2005$ taştan oluşan bir öbekteki taşlardan birini seçip, bu taşı Betül'ün göremeyeceği biçimde işaretliyor ve taşları karıştırıyor. Betül, her hamlede mevcut taşları hiçbiri boş olmayan üç öbeğe ayırıyor. Ali, işaretlediği taşı içermeyen iki öbekten, varsa daha çok taştan oluşanını, her ikisi de aynı sayıda taştan oluşuyorsa, herhangi birini oyundan çıkartıyor ve geri kalan taşları yeniden karıştırıyor. Sıra tekrar Betül'e geliyor ve oyun iki taş kalana kadar bu şekilde sürüyor. İki taş kalınca, Ali, Betül'e hangi taşın işaretli olduğunu söylüyor. Betül, işaretli taşı en az kaç hamlede bulmayı garantileyebilir?

$
\textbf{a)}\ 11
\qquad\textbf{b)}\ 13
\qquad\textbf{c)}\ 17
\qquad\textbf{d)}\ 18
\qquad\textbf{e)}\ 19
$

[geo]

Yanıt: $\boxed A$

Betül'ün herhangi bir hamlesinden önce taş sayısı $n=2k$ gibi bir çift sayı ise Betül en fazla $k-1$ tane taşın oyundan çıkarılmasını garantileyebilir. Gerçekten daha fazla sayıda taşın oyundan çıması için Betül'ün en az $k$ taş içeren bir öbek ayırması gerekir, fakat işaretli taş bu öbekte ise, diğer öbeklerin her birinde en fazla $k-1$ taş olduğundan oyundan çıkarılan taş sayısı da en fazla $k-1$ olacak. Benzer şekilde $n=2k+1$ ise Betül en fazla $k$ taşın çıkarılmasını garantileyebilir. O halde Betül aşağıdaki stratejiyi uygularsa en az hamle sayısına ulaşır: Taş sayısı $2k+1$ ise bunları $k, k, 1$ taş içeren üç öbeğe, taş sayısı $2k$ ise $k, k-1,1$ taş içeren üç öbeğe ayırır. Birinci durumda en az $k$, ikinci durumda da en az $k-1$ taş oyundan çıkarılacak. $2005$ taş için en "kötü" durumda taş sayısı şöyle değişecek:

$2005 \rightarrow 1003 \rightarrow 502 \rightarrow 252 \rightarrow 127 \rightarrow 64 \rightarrow 33 \rightarrow 17 \rightarrow 9 \rightarrow 5 \rightarrow 3 \rightarrow 2$.

Böylece Betül en az $11$ hamlede işaretli taşı bulmayı garantileyebilir.

Kaynak: Sonlu Matematik Olimpiyat Soruları ve Çözümleri, Refail Alizade, Ünal Ufuktepe, 2006. Problem No: 6.46, Sayfa 203.