APMO 2008/functional equation

Discussion on Asian Pacific Mathematical Olympiad (APMO)
Avik Roy
Posts: 156
Joined: Tue Dec 07, 2010 2:07 am

APMO 2008/functional equation

This problem will take a good count on your understanding of numbers.

Consider the function $f: \mathbb{N}_0\to\mathbb{N}_0$, where $\mathbb{N}_0$ is the set of all non-negative
integers, defined by the following conditions :

$(i) f(0) = 0; (ii) f(2n) = 2f(n)$ and $(iii) f(2n + 1) = n + 2f(n)$ for all $n\geq 0$

(a) Determine the three sets $L = \{ n | f(n) < f(n + 1) \}, E = \{n | f(n) = f(n + 1) \},$ and $G = \{n | f(n) > f(n + 1) \}.$
(b) For each $k \geq 0$, find a formula for $a_k = \max\{f(n) : 0 \leq n \leq 2^k\}$ in terms of k.
"Je le vois, mais je ne le crois pas!" - Georg Ferdinand Ludwig Philipp Cantor

Zzzz
Posts: 172
Joined: Tue Dec 07, 2010 6:28 am
Location: 22° 48' 0" N / 89° 33' 0" E

Re: APMO 2008/functional equation

Hint goes first:
Solution:
Every logical solution to a problem has its own beauty.