2019 Antalya Matematik Olimpiyatı Soru 24

[Metin Can Aydemir]

$f(1)=1$ ve her $n$ pozitif tamsayısı için, $$f(2n)=f(n),~~~~~ f(2n+1)=f(n)+1 $$ olduğuna göre, $f(2^{2019}-1019)$ değeri aşağıdakilerden hangisidir?

$\textbf{a)}\ 2013 \qquad\textbf{b)}\ 2018  \qquad\textbf{c)}\ 2017 \qquad\textbf{d)}\ 2011 \qquad\textbf{e)}\ 2021$

[Metin Can Aydemir]

Cevap: $\boxed{D}$

Sorulan fonksiyon değerini hesaplamaya çalışalım, $$f(2^{2019}-1019)=f(2\cdot(2^{2018}-510)+1)=f(2^{2018}-510)+1=f(2^{2017}-255)+1$$ $$f(2^{2017}-255)+1=f(2\cdot(2^{2016}-128)+1)+1=f(2^{2016}-2^{7})+2$$ $$f(2^{2016}-2^{7})+2=f(2^{2009}-1)+2$$ Eğer $f(2^k-1)=k$ olduğunu gösterirsek soru biter. Tümevarımla gösterelim, $f(2^1-1)=1$'dir ve bu eşitlik $\{1,2,\dots,n\}$ için doğru olsun, $n+1$ için ispatlayalım. Soruda verilen ikinci eşitliği kullanırsak, $$f(2^n-1)+1=f(2\cdot(2^{n}-1)+1)\Rightarrow f(2^{n+1}-1)=n+1$$ bulunur, yani her $k$ pozitif tamsayısı için $f(2^{k}-1)=k$'dır. Buradan $$f(2^{2019}-1019)=f(2^{2009}-1)+2=2009+2=2011$$ bulunur.

Not: $(x)_2$ iki tabanında bir sayı olmak üzere, biraz gözlemle $n=(a_ka_{k-1}\dots a_1a_0)_2$ için $f(n)=a_0+a_1+\cdots+a_k$ olduğu da görülebilir.