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

Advertisements

About mathtuition88

http://mathtuition88.com
This entry was posted in math olympiad solution, Uncategorized and tagged , , . Bookmark the permalink.

6 Responses to Solution to HP A4 Printer Paper Mysterious Question

  1. ivasallay says:

    I reached the same conclusion after finding all the values of f(x) up to f(15) = 4 and knowing that f(16) = 1 again, but I still felt a bit unsure of myself. You did a wonderful job proving the answer. Thank you!

    Liked by 1 person

  2. ivasallay says:

    Or at least had as much confidence as you did to post an answer!

    Liked by 1 person

  3. Again, thank you for posting a proof.
    I’m a maths tutor and found the problem interesting when I bought the HP A4 paper last week, and shared it with a student. I liked it because I would like to encourage students to see that doing maths is puzzling over novel challenges and situations, not just getting to grips with the methods on their particular exam syllabus.
    I came to the solution (10) by building up a graph of the function, working step by step from n=1 to n=2 to n=3 onwards, and observed that f(n) peaked, reaching progressively higher maxima at n equal to 7, then 15, then 31, followed by a drop to f(n) equal to 1, and an uneven climb after that.
    I then noticed that 7, 15 and 31 are each one less than a power of 2 i.e. 2^n – 1.
    Then it was satisfying to notice that the height of each new maximum peak was equal to the value of n in 2^n – 1.
    From that, it was a short step to see that 1994 is between 2^10 and 2^11, so the solution had to be 10.
    What I’m interested to know is whether my path to discovering the answer was similar to the paths of others who have found it?
    Deriving the proof demonstrates unequivocally that the answer is right, but I wonder whether only publishing the proof might give the impression to inquisitive maths students having a go at the problem, that deriving the proof was how the answer (10) was found. I’d bet that you found the answer by a similar exploratory route to me, and set about deriving a proof afterwards. Am I right?
    Also, as I came to my conjecture that the answer was 10 by inspecting f(n) as far as n=50 by hand on graph paper, I then decided to work out how to use an Excel spreadsheet to find all the values of f(n) from n=1 to n=1994.
    (This turns out to need dynamic cell referencing.)
    I got Excel to give me all the values of f(n) by first filling cells in column A in turn with 1,2,3 … up to 1994.
    I used column B for each value of f(n).
    The first row of column B I filled with 1 as given in the problem. I figured that an Excel function that would work would be one which would test whether the current row was odd or even. If even, the function would need to return the value of the cell in the row whose number was half the current row ( as f(n) = f(2n) was stated in the problem). Otherwise the current row number must be odd, and so the Excel function would need to return the value of 1 more than the previous row ( as f(2n+1)=f(2n) +1 ).
    After some googling to find out how to dynamically make cell references – which turns out to be the INDIRECT function – I worked out this formula which worked, when I copied it down all the cells in column B starting from row 2 up to row 1994.
    =IF(ISEVEN(A2), INDIRECT(“B”&(ROW()/2)), B1 + 1).

    Liked by 1 person

    • Hi Jonathan, thanks for your detailed comment! “I’d bet that you found the answer by a similar exploratory route to me, and set about deriving a proof afterwards. Am I right?” Yes, you are right indeed! My favorite approach to solving questions is Construct Examples, Find Patterns, and write a proof!
      I hope you and your student enjoyed solving this problem as much as I did.

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s