APMO 2008/functional equation

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

APMO 2008/functional equation

Unread post by Avik Roy » Thu Feb 03, 2011 4:45 pm

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

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

Re: APMO 2008/functional equation

Unread post by Zzzz » Fri Feb 04, 2011 10:30 am

Hint goes first:
Find the values of $f(1),f(2),f(3),...,f(16)$. It is easy to 'see' the sets $L,E,G$ and values of $a_k$s. Now prove using induction or contradiction :)
(a) Notice that $L,G,E$ are mutually disjoint sets.
Let $n$ is an even number $n=2k,\ k>0$
\[\Rightarrow f(2k)<f(2k+1)\]
\[\Rightarrow f(n)<f(n+1)\]
So, $n\in L$ i.e $S_e=\{n|n=2k,\ k\in \mathbb N\}\subset L\ ...\ (1)$

We claim that for all odd $n,\ f(n)\ge f(n+1)$
Here is the proof:
We can prove it by strong induction. Finding values of $f(1),f(3)$ we can see that this is true for $n\le 3$. Let its true for all odd $n\le m=2k+1$
If $k$ is even, as $k+1<m$ and its odd, $f(k+1)\ge f(k+2) \Rightarrow 2f(k+1)+k+1\ge 2f(k+2)$.
If $k$ is odd, let $k+1=2l$. Now, $2f(k+1)+k+1=2f(2l)+2l=4f(l)+2l\ge 4f(l)+2l=2(2f(l)+l)=2f(2l+1)=2f(k+2)$
Now, for both odd and even $k$, \[2f(k+1)+k+1\ge 2f(k+2)\]
\[\Rightarrow f(2(k+1)+1)\ge f(2(k+2))\]
\[\Rightarrow f(2k+3)\ge f(2k+4)\]
\[\Rightarrow f(m+2)\ge f(m+3)\]
So, our claim is true for $n=m+2$ as well. So, for all odd $n,\ f(n)\ge f(n+1)$

Now, Let $n=4k+3$
As, $2k+1$ an odd number,
\[f(2k+1) \ge f(2k+2)\]
\[\Rightarrow 2f(2k+1)+2k+1>2f(2k+2)\]
\[\Rightarrow f(2(2k+1)+1)>f(2(2k+2)\]
\[\Rightarrow f(4k+3)>f(4k+4)\]
\[\Rightarrow f(n)>f(n+1)\]
\[\therefore n \in G\]
So, $S_3=\{n|n=4k+3,\ k\in \mathbb N\} \subset G\ ...\ (2)$

Now, Let $n=4k+1$
\[ 2k+4f(k)=2(k+2f(k))\]
\[\Rightarrow 2k+2f(2k)=2f(2k+1)\]
\[\Rightarrow f(2\cdot 2k +1)=f(2(2k+1))\]
\[\Rightarrow f(4k+1)=f(4k+2)\]
\[\Rightarrow f(n)=f(n+1)\]
So, $n \in E.\ 0$ is also an element of $E$.
$\therefore S_1=\{n|n=4k+1,\ k\in \mathbb N\}\cup \{0\} \subset E\ ...\ (3)$

$S_e \cup S_1 \cup S_3 = \mathbb N_0$ and $L,E,G$ are mutually disjoint. So from $(1),(2),(3)$
$\{n|n=2k,\ k\in \mathbb N\}=L;\ \{n|n=4k+3,\ k\in \mathbb N\}=G;\ \{n|n=4k+1,\ k\in \mathbb N\}\cup {0}=E$
Every logical solution to a problem has its own beauty.
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)

Post Reply