Yalnızca $1,2,3$ kullanılarak yazılabilen sayılar (Tübitak Lise 2013)

Question

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$

 

 

Kaynak: Tübitak Lise Matematik Olimpiyatı 1. Aşama Soru 32. (Sevdiğim bir problemdir, bir süre sonra ben de çözümümü ekleyeceğim.)

 

Comments

list = Permutations[ Flatten@{ConstantArray[1, 5], ConstantArray[2, 5],    ConstantArray[3, 5]}, {10}];
list = Cases[list, {1, 2 | 3, __, 2 | 3, 1}];
3 Length@Complement[list, Cases[list, {__, x_, x_, __}]]

510

 

Answer 1

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ü