Tübitak Lise 1. Aşama 2010 Soru 20

[ERhan ERdoğan]

$0$ sayısı ile başlanıp, her adımda bir önceki sayının $1$ fazlası veya $2$ katı alınarak, aşağıdaki sayılardan hangisini en az sayıda adımda elde edilir?

$
\textbf{a)}\ 2011
\qquad\textbf{b)}\ 2010
\qquad\textbf{c)}\ 2009
\qquad\textbf{d)}\ 2008
\qquad\textbf{e)}\ 2007
$

[Metin Can Aydemir]

Cevap: $\boxed{D}$

Çözüm 1: Soruyu çözmek için verilen sayılardan $1$ çıkartarak veya $2$'ye bölerek $0$'a ulaşmaya çalışabiliriz. Eğer sayı tekse $1$ çıkarmak zorundayız. Çift sayıda ise ikiye bölmenin daha avantajlı olduğunu gösterelim. Aksini varsayalım ve çift $2n$ sayısından $2k$ defa $1$ çıkardıktan sonra $2$'ye bölmenin daha avantajlı olduğunu kabul edelim (çift sayıda $1$ çıkarmamız gerektiği barizdir). Bu durumda $2k+1$ hamle yaparak $n-k$ sayısına ulaşmış oluruz. Onun yerine önce $2$'ye bölseydik ve $k$ adet $1$ çıkarsaydık $k+1$ hamlede $n-k$'ya ulaşacaktık. Yani çift sayı denk gelirse $2$'ye bölmeliyiz.

$2011\to 2010\to 1005\to 1004\to 502\to 251\to 250\to 125\to 124\to 62\to 31\to 30\to 15\to 14\to 7\to 6\to 3\to 2\to 1\to 0$

$2010\to 1005\to 1004\to 502\to 251\to 250\to 125\to 124\to 62\to 31\to 30\to 15\to 14\to 7\to 6\to 3\to 2\to 1\to 0$

$2009\to 2008\to 1004\to 502\to 251\to 250\to 125\to 124\to 62\to 31\to 30\to 15\to 14\to 7\to 6\to 3\to 2\to 1\to 0$

$2008\to 1004\to 502\to 251\to 250\to 125\to 124\to 62\to 31\to 30\to 15\to 14\to 7\to 6\to 3\to 2\to 1\to 0$

$2007\to 2006\to 1003\to 1002\to 501\to 50\to 250\to 125\to 124\to 62\to 31\to 30\to 15\to 14\to 7\to 6\to 3\to 2\to 1\to 0$

Sonuç olarak en az hamleyle $2008$ elde edilebilir.

Çözüm 2: Eğer $2$ tabanında düşünürsek $1$ eklemek son basamağı $0$'dan $1$'e çevirmek ve $2$ ile çarpmak sona bir adet $0$ eklemek olacaktır. Bu durumda olası en küçük hamle sayısı $n=(a_ka_{k-1}\cdots a_1a_0)_2$ için $a_i$'lerdeki $1$ sayısı $t$ ise $k+t-1$ olacaktır. Verilen sayıları $2$ tabanında yazarsak en küçük hamle sayısını bulabiliriz.