Tübitak Ortaokul 1. Aşama 2012 Soru 29

[Egemen]

$1\times 17$ bir satranç tahtasının karelerine $1,2,\ldots ,17$ sırayla ve 1'den sonraki her sayı daha önce yazılmış sayılardan birine komşu olmak koşuluyla kaç farklı şekilde yazılabilir?

$\textbf{a)}\ 45680 \qquad\textbf{b)}\ 65536 \qquad\textbf{c)}\ 70246 \qquad\textbf{d)}\ 81246\qquad\textbf{e)}\ \text{Hiçbiri}$

[Eray]

Yanıt: $\boxed{B}$

$1$ sayısı rastgele bir haneye yazılsın. Yazıldığı haneden sağa ve sola doğru sayılar artan sırada olacaktır. Örneğin:



Yeterince açık değil ise kendiniz birkaç dizilim oluşturmayı deneyin, fark edeceksinizdir.

Şimdi, toplam kaç farklı dizilim oluşturulabileceğini bulalım.
$1$ sayısı, başta $k-1$ hane boş olmak üzere $k.$ haneye konulsun. Kalan $16$ sayıdan baştaki hanelere gelecek olan $k-1$ tanesi $\binom{16}{k-1}$ farklı şekilde seçilirse, bunlar artan sırada tek biçimde dizilebilir. Kalan $17-k$ adet sayı bellidir ve kalan hanelerde artan sırada olmaları gerektiğinden tek şekilde dizileceklerdir.
Yani, $1$ sayısı baştan $k.$ haneye konulursa, $\binom{16}{k-1}$ farklı dizilim meydana gelmektedir.
$\sum \limits_{k=1}^{17} \binom{16}{k-1} = \binom{16}{0}+\binom{16}{1}+\cdots+\binom{16}{16}=2^{16}=65536$ farklı dizilim vardır.