Tübitak Lise 1. Aşama 2020 Soru 19

[Eray]

Bir $f: \mathbb{Z}^{+} \rightarrow \mathbb{Z}^{+} \cup\{0\}$ fonksiyonu $f(1)=f(2)=0$ ve her $n$ pozitif tam sayısı için
$$f(3 n)=f(n)+1\quad \text{ve}\quad f(3 n+1)=f(3 n+2)=f(n)$$
koşullarını sağlıyor. Buna göre $f\left(\dfrac{3^{2020}-1}{8}\right)$ kaçtır?

$
\textbf{a)}\ 504
\qquad\textbf{b)}\ 673
\qquad\textbf{c)}\ 1009
\qquad\textbf{d)}\ 2019
\qquad\textbf{e)}\ 3029
$

[Metin Can Aydemir]

Cevap: $\boxed{C}$

Bizden fonksiyondaki görüntüsü istenen değeri inceleyelim. $$\dfrac{3^{2020}-1}{8}=\dfrac{(3^2)^{1010}-1}{3^2-1}=(3^2)^{1009}+(3^2)^{1008}+\cdots +(3^2)^{1}+(3^2)^{0}=3^{2018}+3^{2016}+\cdots +3^{2}+1$$ olur. Bu sayıyı $3$ tabanında yazacak olursak $1010$ tane $1$ ve $1009$ tane $0$ olmak üzere, $$\dfrac{3^{2020}-1}{8}=\left (1010\dots 0101\right )_{3} $$ elde ederiz. Fonksiyona dönecek olursak $n=\left ( a_1a_2\dots a_k\right )_3$ olmak üzere,

Eğer $a_k=1$ veya $a_k=2$ olursa $$f \left ( \left ( a_1a_2\dots a_k\right )_3 \right )=f \left ( \left ( a_1a_2\dots a_{k-1}\right )_3 \right )$$ olacaktır.

Eğer $a_k=0$ olursa $$f \left ( \left ( a_1a_2\dots a_k\right )_3 \right )=f \left ( \left ( a_1a_2\dots a_{k-1}\right )_3 \right )+1$$ olacaktır. Yani $n$ sayısının $3$ tabanındaki halinin sağından başlayarak rakamları atıp $f(1)$ veya $f(2)$'ye ulaşabiliriz. $1$ fazlalık sadece $0$ rakamıyla karşılaşılınca ekleneceğinden $f(n)$ değeri $n$'nin $3$ tabanındaki halinde bulunan $0$ rakamının sayısına eşit olacaktır. Bizden istenen değerde $1010$ tane $1$, $1009$ tane $0$ vardır. Dolayısıyla, $f\left (\dfrac{3^{2020}-1}{8}\right )=1009$ olacaktır.