Tübitak Lise 1. Aşama 2008 Soru 36

[ERhan ERdoğan]

Üst üste dizilmiş $2008$ madeni paranın bulunduğu bir beyaz masa ve iki boş siyah masadan başlayarak, her hamlede herhangi bir masadaki en üst pozisyondaki parayı alıp herhangi bir boş masaya veya herhangi bir masadaki en üst pozisyona yerleştirerek, en az kaç hamlede tüm paralar beyaz masaya ters sırada yerleştirilebilir?

$
\textbf{a)}\ 6016
\qquad\textbf{b)}\ 6017
\qquad\textbf{c)}\ 6022
\qquad\textbf{d)}\ 6023
\qquad\textbf{e)}\ 6024
$

[geo]

Yanıt: $\boxed C$

Cevap: $6022$. $n$ tane madeni para için cevabın $3n-2$ olduğunu kanıtlayacağız. İlk olarak bunun için $3n-2$ hamlenin yeterli olduğunu gösterelim. Beyaz masa $B$, diğer masalar $S_1$ ve $S_2$ olsun. En üstteki parayı $S_1$ e, kalan paraları $S_2$ ye, $S_1$ deki parayı $B$ ye, $S_2$ deki $n-1$ tane paranın $n-2$ tanesini $S_1$ e, $S_2$ deki tek parayı $B$ ye ve $S_1$ deki paraları $B$ ye yerleştirirsek paralar $1+(n-1)+1+(n-2)+1+(n-2)=3 n-2$ hamle sonucunda beyaz masaya ters sırada yerleşmiş olur. Şimdi gereken hamle sayısının $3 n-2$ den az olamayacağını gösterelim. Her madeni paraya hamle uygulanacağı için $2$ den az hamle uygulanmış madeni para yoktur. Toplam hamle sayısı $3 n-2$ den az olursa, $2$ hamle uygulanmış en az $3$ madeni para olacaktır. Bu $3$ madeni paranın ikisi aynı siyah masaya taşınmıştır ve demek ki hamleler bittiğinde bu iki paranın $B$ masasındaki sıraları değişmemiştir, çelişki.

Kaynak: Tübitak 16. Ulusal Matematik Olimpiyatı Birinci Aşama Sınav Soru ve Çözümleri 2008