math olympiad solution – Singapore Maths Tuition

A while ago, I posted the HP A4 Paper Mysterious Question which goes like this:

Problem of the Week

Suppose $f$ is a function from positive integers to positive integers satisfying $f(1)=1$ , $f(2n)=f(n)$ , and $f(2n+1)=f(2n)+1$ , for all positive integers $n$ .

Find the maximum of $f(n)$ when $n$ is greater than or equal to 1 and less than or equal to 1994.

So far no one seems to have solved the question on the internet yet!

I have given it a try, and will post the solution below!

If you are interested in Math Olympiad, it is a good idea to invest in a good book to learn more tips and tricks about Math Olympiad. One excellent Math Olympiad author is Titu Andreescu, trainer of the USA IMO team. His book 104 Number Theory Problems: From the Training of the USA IMO Team is highly recommended for training specifically on Number Theory Olympiad questions, one of the most arcane and mysterious fields of mathematics. He does write on other Math Olympiad subjects too, like Combinatorics, so do check it out by clicking the link above, and looking at the Amazon suggested books.

Now, to the solution of the Mysterious HP A4 Paper Question:

We will solve the problem in a few steps.

Step 1

First, we will prove that $\boxed{f(2^n-1)=n}$ . We will do this by induction. When $n=1$ , $f(2^1-1)=f(1)=1$ . Suppose $f(2^k-1)=k$ . Then,

$\begin{aligned} f(2^{k+1}-1)&=f(2(2^k)-1)\\ &=f(2(2^k-1)+1)\\ &=f(2(2^k-1))+1\\ &=f(2^k-1)+1\\ &=k+1 \end{aligned}$

Thus, we have proved that $f(2^n-1)=n$ for all integers n.

Step 2

Next, we will prove a little lemma. Let $g(x)=2x+1$ . We will prove, again by induction, that $\boxed{g^n (1)=2^{n+1}-1}$ . Note that $g^n(x)$ means the composition of the function g with itself n times.

Firstly, for the base case, $g^1(1)=2+1=3=2^2-1$ is true. Suppose $g^k (1)=2^{k+1}-1$ is true. Then, $g^{k+1}(1)=2(2^{k+1}-1)+1=2^{k+2}-1$ . Thus, the statement is true.

Step 3

Next, we will prove that if $y<2^n-1$ , then $f(y)<n$ . We will write $y=2^{\alpha_1}x_1$ , where $x_1$ is odd. We have that $x_1<2^{n-\alpha_1}$ .

$\begin{aligned} f(y)&=f(2^{\alpha_1} x_1)\\ &=f(x_1) \end{aligned}$

Since $x_1$ is odd, we have $x_1=2k_1+1$ , where $k_1<2^{n-\alpha_1-1}$ .

Continuing, we have

$\begin{aligned} f(x_1)&=f(2k_1+1)\\ &=f(2k_1)+1\\ &=f(k_1)+1 \end{aligned}$

We will write $k_1=2^{\alpha_2}x_2$ , where $x_2$ is odd. We have $x_2<2^{n-\alpha_1-\alpha_2-1}$ .

$\begin{aligned} f(k_1)+1&=f(2^{\alpha_2}x_2)+1\\ &=f(x_2)+1 \end{aligned}$

where $x_2=2k_2+1$ , and $k_2<2^{n-\alpha_1-\alpha_2-2}$ .

$\begin{aligned} f(x_2)+1&=f(2k_2)+1+1\\ &=f(k_2)+2\\ &=\cdots\\ &=f(k_j)+j \end{aligned}$

where $k_j=1$ , $1=k_j<2^{n-\alpha_1-\alpha_2-\cdots-\alpha_j-j}$ .

Case 1: All the $\alpha_i$ are 0, then $y=2(\cdots 2(k_j)+1=g^j(1)=2^{j+1}-1$ . Then, $j+1<n$ , i.e. $j<n-1$ .

Thus, $f(y)=f(k_j)+j<1+n-1=n$ .

Case 2: Not all the $\alpha_1$ are 0, then, $1=k_j<2^{n-\alpha_1-\alpha_2-\cdots-\alpha_j-j}\leq 2^{n-j-1}$ . We have $2^0=1<2^{n-j-1}$ , thus, $0<n-j-1$ , which means that $j<n-1$ . Thus, $f(y)=f(k_j)+j<1+n-1=n$ .

Step 4 (Conclusion)

Using Step 1, we have $f(1023)=f(2^{10}-1)=10$ , $f(2047)=f(2^{11}-1)=11$ . Using Step 3, we guarantee that if $y<2047$ , then $f(y)<11$ . Thus, the maximum value of f(n) is 10.