Solution to HP A4 Printer Paper Mysterious Question

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.

Ans: 10