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

[alpercay]

Yalnızca $1, 2, 3$ rakamları kullanılarak, ilk ve son basamaklarında aynı rakam yer alan ve herhangi ardışık iki basamağında aynı rakam yer almayan kaç farklı $10$ basamaklı pozitif tam sayı yazılabilir?

$
\textbf{a)}\ 768
\qquad\textbf{b)}\ 642
\qquad\textbf{c)}\ 564
\qquad\textbf{d)}\ 510
\qquad\textbf{e)}\ 456
$

[geo]

Yanıt: $\boxed{D}$

Ardışık basamakları farklı olup $1$ ile başlayıp $1$ ile biten $n$ basamaklı sayıların sayısını $a_n$ ile gösterelim. Açık şekilde $a_3 = 2$ ve sorumuzun cevabı $3a_{10}$.
$1$ ile başlayan; ama son basamağına bir kısıtlama getirilmemiş sayıların sayısı: $2^{n-1}$.
Bu durumda $1$ ile başlayıp $1$ ile bitmeyen söz konusu $n$ basamaklı sayıların sayısı $2^{n-1} - a_n$ olacaktır.
Bu sayının sonuna $1$ koyarsak, $n+1$ basamaklı $1$ ile başlayıp $1$ ile biten sayı elde edeceğiz.
O halde $a_{n+1} = 2^{n-1}-a_n$.
Açık şekilde, $a_4 = 2^2 - 2$, $a_5 = 2^3 - a_4 = 2^3 - 2^2 + 2$ ve $a_6 = 2^4 - 2^3 + 2^2 - 2$.
O halde $a_{10} = 2^8 - 2^7 + 2^6 -2^5 + 2^4 - 2^3 + 2^2 - 2^1$.
$\dfrac{a_{10}}2 = 2^7 - 2^6 + 2^5 - 2^4 + 2^3 - 2^2 + 2^1 - 1$ ile $a_{10}$ u toplarsak $\dfrac{3a_{10}}2  = 2^8 - 1 \Rightarrow 3a_{10} = 2^9 - 2 = 510$.

[Lokman Gökçe]

Yanıt: $\boxed{D}$

Daha önce şurada daire diliminin boyanması problemini çözerek $n\geq 4$ için $a_{n+1}+a_n = k\cdot (k-1)^{n-1}$ indirgeme bağıntısını ve $a_n = (k-1)(-1)^n + (k-1)^n $ açık biçimini elde etmiştik.

Yukarıdaki problemde de $1,2,3$ rakamlarını kullanarak istenen özellikte yazılabilecek $n$ basamaklı sayıların sayısını $b_n$ ile gösterelim. Bizden istenen $b_{10}$ değeridir. İlk basamak ile $n$-inci basamak aynı olması istendiğinden, ilk basamak belirlendiğinde $n$-inci basamak da belirlenmiş oluyor. Bu sebeple ilk $n-1$ basamakla ilgilenmeliyiz. Daire dilimi boyama problemi ile ikişki kurarsak, $1,2,3$ rakamları ile $n-1$ basamaklı sayı yazma problemi $k=3$ renk ile $n-1$ daire dilimini boyama ile özdeştir. Bu sebeple $n-1$ basamağın belirlenme sayısı $b_n = a_{n-1}$ dir. O halde problemimizin çözümü $a_9$ olacaktır. $k=3$ iken

$$ a_n = 2\cdot (-1)^n + 2^n $$
olup $a_9=2\cdot (-1)^9 + 2^9 = -2 + 512 = 510$ bulunur.



Not:
Ayrıca daha fazla uygulama problemiyle ilgilenenler için burada video olarak şunları sundum:

1. $a_{n+1}+a_n = k\cdot (k-1)^{n-1}$ bağıntısının ispatı

2. 2019 JEE (Joint Entrance Exam) isimli sınava ait bir problemin çözümü

3. 2013 Tübitak Lise 1. Aşama 32. sorunun çözümü

4. Çetin ceviz bir kombinatorik problemin çözümü