Bài toán 35 : Tìm $f:\mathbb{N}\rightarrow \mathbb{N}$ thỏa :
$i)f(1)=1$
$ii) f(2n+1)=f(2n)+1$
$iii)f(2n)=3f(n)$
Giải :
Từ $ii)$ và $iii)$ ta thấy $f(2n)=3f(n)$ và $f(2n+1)=3f(n)+1$
Nên $n\equiv 0\pmod{2}\Rightarrow f(n)\equiv 0\pmod{3}$ và $n\equiv 1\pmod{2}\Rightarrow f(n)\equiv 1\pmod{3}$ $(*)$
Cho $n=\left (\overline{a_na_{n-1}a_{n-2}...a_1a_0} \right )_2$ ( $a_i \in \left \{ 0;1 \right \}$ và $a_n=1$ )
Và $f(n)=\left (\overline{b_mb_{m-1}b_{m-2}...b_1b_0} \right )_3$ ( $b_i\in \left \{ 0;1;2 \right \}$ và $b_n=1$ )
Ta có $\left (\overline{a_na_{n-1}a_{n-2}...a_{i+1}a_i} \right )_2=2 \cdot \left (\overline{a_na_{n-1}a_{n-2}...a_{i+1}} \right )_2 +a_i$
Và $\left (\overline{b_mb_{m-1}b_{m-2}...b_{i+1}b_i} \right )_3=3 \cdot \left (\overline{b_mb_{m-1}b_{m-2}...b_{i+1}} \right )_3 +b_i$
Chứng minh theo qui nạp ta chứng minh được $a_i=b_i$ (theo $(*)$) và chứng minh được $m=n$ (do $f(1)=1$)
Vậy nên ta xác lập hàm $f$ bằng cách:
Chuyển $n=\left (\overline{a_na_{n-1}a_{n-2}...a_1a_0} \right )_2$ thì $f(n)=\left (\overline{a_na_{n-1}a_{n-2}...a_1a_0} \right )_3$
Bài viết đã được chỉnh sửa nội dung bởi namcpnh: 21-06-2013 - 10:47