IMO Shortlist 2000 problem A4
Dodao/la:
arhiva2. travnja 2012. The function
![F](/media/m/3/e/8/3e8bad5df716d332365fca76f53c1743.png)
is defined on the set of nonnegative integers and takes nonnegative integer values satisfying the following conditions: for every
(i)
(ii)
(iii)
Prove that for each positive integer
![m,](/media/m/d/4/8/d4801e2df194f69b71c59917ecff5fcf.png)
the number of integers
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
with
![0 \leq n < 2^m](/media/m/4/3/6/436e8c4d0efab6598ddc9ffa830c2ac0.png)
and
![F(4n) = F(3n)](/media/m/9/c/3/9c3f52217381a12523bdd55037c391a0.png)
is
%V0
The function $F$ is defined on the set of nonnegative integers and takes nonnegative integer values satisfying the following conditions: for every $n \geq 0,$
(i) $F(4n) = F(2n) + F(n),$
(ii) $F(4n + 2) = F(4n) + 1,$
(iii) $F(2n + 1) = F(2n) + 1.$
Prove that for each positive integer $m,$ the number of integers $n$ with $0 \leq n < 2^m$ and $F(4n) = F(3n)$ is $F(2^{m + 1}).$
Izvor: Međunarodna matematička olimpijada, shortlist 2000