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

Author: mathtuition88

Math and Education Blog View all posts by mathtuition88

8 thoughts on “Solution to HP A4 Printer Paper Mysterious Question”

ivasallay says:

March 20, 2015 at 11:41 pm

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!

LikeLiked by 1 person

Reply
1. mathtuition88 says:
  
  March 20, 2015 at 11:46 pm
  
  Thanks for reading the solution! It’s strange no one else on the Internet is interested in solving the HP printer paper question!
  
  LikeLiked by 1 person
  
  Reply
ivasallay says:

March 21, 2015 at 1:13 am

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

LikeLiked by 1 person

Reply
1. mathtuition88 says:
  
  March 21, 2015 at 10:43 am
  
  Thanks! I just realized this problem is a little similar to the Collatz Conjecture, a famous unsolved problem! Math is mysterious indeed.
  
  LikeLike
  
  Reply
Jonathan Rigby says:

September 13, 2015 at 5:53 pm

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).

LikeLiked by 1 person

Reply
1. mathtuition88 says:
  
  September 13, 2015 at 6:10 pm
  
  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.
  
  LikeLike
  
  Reply
Pingback: HP Printer Paper Mysterious Math Problem | Singapore Maths Tuition
Chinoiseries2014 says:

September 11, 2018 at 6:01 pm

Reblogged this on Math Online Tom Circle.

LikeLike

Reply

Step 1

Step 2

Step 3

Step 4 (Conclusion)

Share this:

Like this:

Related

Author: mathtuition88

8 thoughts on “Solution to HP A4 Printer Paper Mysterious Question”

Leave a Reply Cancel reply