Tübitak Lise 1. Aşama 2014 Soru 27

[ERhan ERdoğan]

Pozitif tam sayılarda tanımlı bir $f$ fonksiyonu, $f(1)=4$ ve her $n$ pozitif tam sayısı için $f(2n)=f(n)$ ve $f(2n+1)=f(n)+2$ koşullarını sağlamaktadır. $2014$ ten küçük kaç $k$ pozitif tam sayısı için $f(k)=8$ dir?

$
\textbf{a)}\ 45
\qquad\textbf{b)}\ 120
\qquad\textbf{c)}\ 165
\qquad\textbf{d)}\ 180
\qquad\textbf{e)}\ 215
$

[Egemen]

Yanıt: $\boxed{C}$

(Egemen Erbayat)

$f(1)=4 \Rightarrow k \in \mathbf N ,  f(2^k)=4$


$f(2^k)=4 \Rightarrow  f(2^k)+2=f(2(2^k)+1)=f(2^{k+1}+1)=6$


$f(2^{k+1}+1)=6 \Rightarrow  m \in \mathbf N ,   f((2^m)(2^{k+1}+1))=6= f(2^{k+m+1}+2^m)$


$f(2^{k+m+1}+2^m)=6 \Rightarrow f(2^{k+m+1}+2^m)+2=f(2(2^{k+m+1}+2^m)+1)=f(2^{k+m+2}+2^{m+1}+1)=8 $


$f(2^{k+m+2}+2^{m+1}+1)=8 \Rightarrow  \ell \in \mathbf N ,   f((2^\ell)(2^{k+m+2}+2^{m+1}+1))=8= f(2^{k+m+\ell+2}+2^{m+\ell+1}+2^\ell)$

$2^{k+m+\ell+2}+2^{m+\ell+1}+2^\ell  \lt 2014$

$g(k,m,\ell) = 2^{k+m+\ell + 2} + 2^{m+\ell + 1} + 2^{\ell} < 2014 = \underbrace{(1111011110)_2}_{11 \text{ basamaklı}}$
$g(k,m,\ell)$; $2$ tabanında en fazla $11$ basamaklı sayılardan tam olarak $3$ tane $1$ içerenlerin sayısıdır. $\dfrac{11!}{8! \cdot 3!} = 165$.