Elementary, my dear Watson

On last week’s “Welcome to the math olympics”, I closed with a problem from the International Math Olympiad of 1981 (a bad year for wine – I would know, I was an avid drinker back then). I would like to take some time to present a solution to this problem, because this is where all the magic happens. What magic? You will see. Here is the problem again:

Problem 6 (IMO 1981, modified): If $f(0,y) = y+1, \, f(x+1,0) = f(x,1)$ and $f(x+1,y+1) = f(x, f(x+1,y))$ , for all non-negative integers $x,y$ , find $f(4,2009)$ .

The solution that follows uses solely elementary mathematics. What does that mean? It means that a 15 year-old can figure out the solution, given enough time and an IQ of 300. And, indeed, there are some who can solve this problem in 15 minutes. But, as you will see, it takes clarity of mind that is only attained through relentless effort. Effort to the outside world – to you, it will feel like you are going down the rabbit-hole and you don’t want the journey to end. But you must enter this world with wonder, because it is the world of the imagination – a world where your greatest weapon is your curiosity, prodding your mind to see how far the rabbit-hole goes.

Enter the rabbit-hole: The first thing you observe is that the function $f(x,y)$ has two arguments (inputs) and that you are given three equations that work as an algorithm for computing the value of this function on non-negative integers (0,1, 2, …, etc.) So, where do you start? Usually, you start with almost nothing, near the bottom and then work your way up. But why should you start near 0? Because you soon find that if you try to evaluate $f(4,2009)$ , or even $f(4,2)$ , you get stuck. And getting stuck is the single greatest motivating force to make you think (wouldn’t that be nice). So we must think. “Can I evaluate $f(1,0)$ ?”, for example. Let me stop to say something that is probably obvious to those with math and science backgrounds: evaluate means calculate an answer that will return a number, like 2, or 5, but not $f(2,13)$ . The latter is a function with two inputs and unless you are given a prescription for how that function works (i.e. what number comes out for each pair of inputs), then you might as well think of it as a string of symbols and numbers – in other words, useless. OK, back to computing $f(1,0)$ . You have three equations you can use: $f(0,y) = y+1, \, f(x+1,0) = f(x,1)$ and the complicated-looking $f(x+1,y+1) = f(x,f(x+1,y))$ . Which one to use… You try the first one: $f(0,y) = y+1$ . Can it help you to compute $f(1,0)$ ? Nope. The first input is always 0 in that equation and you are asking for the value of the function when the first input is 1. So, you try the second equation: $f(x+1,0) = f(x,1)$ . Bingo. Choose $x=0$ and substitute on both sides of the equation to get: $f(1,0) = f(0,1)$ . And you are in business! Why? Because now you can use the first equation to get $f(1,0) = f(0,1) = 1+1=2$ (the last equality follows from deep mathematics).

For very large values of 1.

So far, you have seen how to use two of the equations to evaluate $f(1,0)$ . Can you evaluate $f(1,1)$ ? The first two equations are useless, since either the first or second input is always 0. You must use the third one by setting $x=0, y=0$ : $f(1,1) = f(0,f(1,0)) = f(0,2) = 2+1=3$ , where you used $f(1,0)=2$ for the second equality and applied the first equation to get the last equality. Sweet stuff. Now you can try to evaluate either $f(2,1)$ , or $f(1,2)$ . You try $f(2,1)$ using the third equation with $x=1,y=0$ : $f(2,1)=f(1,f(2,0))$ . You don’t know what $f(2,0)$ is, so you try to figure it out using the second equation with $x=1,y=0$ : $f(2,0) = f(1,1) = 3$ (you evaluated $f(1,1)$ a few lines back). Going back to $f(2,1) = f(1,f(2,0)) = f(1,3)$ , you see that you need to figure out what $f(1,3)$ is, which seems more complicated than $f(1,2)$ (you chose to evaluate $f(2,1)$ instead and look where it got you… oh well). At this point you have two choices: Be stubborn and try to figure out $f(1,3)$ (you really want to know what $f(2,1)$ is and I can’t blame you), or switch gears and do the wise thing: Evaluate the simpler $f(1,2)$ . Wisdom be damned. You are forging ahead with $f(1,3)$ using the third equation with $x=0, y=2$ : $f(1,3) = f(0,f(1,2))=f(1,2)+1$ . Did you see what you just did there? You used the first equation in the last equality with $y=f(1,2)$ even though you don’t know what $f(1,2)$ is yet (which is totally your fault). Now, a super-genius would notice that there is a pattern here whenever $x=1$ as an input: $f(1,y+1) = f(0,f(1,y)) = f(1,y)+1$ , where you used the third equation and then the first equation. Time to go wild, you think:
$f(1,y+1) = f(1,y) +1 = (f(1,y-1)+1)+1 = f(1,y-1)+2 = \ldots = f(1,1)+y=3+y.$
For any non-negative integer y! I bet you are wondering how you went from $f(1,y+1) = f(1,y-1)+2$ all the way to $f(1,y+1) = f(1,1)+y = 3+y$ . I will tell you if you give this post 5 stars. Go ahead, it’s free and it will mean so much to my parents (who don’t even know about this blog…) OK, here is the answer: Pattern recognition. Again. Let’s make it explicit: $f(1,y+1) = f(1,y)+1=f(1,y-1)+2 = f(1,y-2) + 3 =\ldots = f(1,1) + ?$ . What should we put instead of the question mark? If you stare enough at the series of equalities, you will notice that the sum of the second argument and the number at the end is always $y+1$ (think about why this is the case). So $?=y$ and $f(1,y+1)=f(1,1)+y = y+3$ .

Yes, I have cleared all levels of Angry Birds with 3 stars! Me and 10 million others.

You didn’t see the pattern right away, but after you evaluated $f(1,y)$ for $y$ up to 5, you noticed that the answer was always $y+2$ and then proved it using the reasoning from the previous paragraph. You have cleared the first level!

Level 2 Mission: Figure out $f(2,y)$ for arbitrary non-negative integers $y$ .

You have built enough intuition by now to see what you need to do next: figure out a general formula for $f(2,y)$ , just like you did for $f(1,y)$ . But how? Well, using the third equation again: $f(2,y) = f(1,f(2,y-1)) = f(2,y-1)+2$ , where you used your knowledge of the general formula for $f(1,z)$ and put $z=f(2,y-1)$ to get the last equality. And it is time to go wild once more:

$f(2,y)=f(2,y-1)+2=f(2,y-2)+2\cdot 2=\ldots = f(2,0)+2y = 2y+3.$

BAM! Level 2 cleared. Let’s get through Level 3 using your experience points from Level 2: $f(3,y) = f(2,f(3,y-1)) = 2f(3,y-1)+3$ . This looks a bit more complicated than before… But you are even more curious than you are stubborn and you want to know; you must know. So you go even wilder this time:

$f(3,y)=2f(3,y-1)+3 = 2(2f(3,y-2)+3)+3 = 2(2(2f(3,y-3)+3)+3)+3 =\ldots = 2^z f(3,y-z) + 3\cdot(1+2+2^2+2^3+\ldots+2^{z-1}) = 2^y f(3,0)+3(1+2+2^2+\ldots+2^{y-1}).$

If you only knew how to evaluate $f(3,0)$ … You do! Use the second equation given to you: $f(3,0)=f(2,1)=2\cdot1+3=5$ , where you used $f(2,y)=2y+3$ from Level 2. Recalling that $1+2+2^2+\ldots+2^{y-1} =2^y-1$ (see Deal or no deal?), you get:

$f(3,y) = 2^y\cdot 5+ 3(2^y-1) = 2^y\cdot (5+3) -3 = 2^{y+3}-3.$

And Level 3 is cleared and you are ready for the final boss. But you have the Eye of Thundera (the scary-looking equation $f(x+1,y+1)=f(x,f(x+1,y))$ turned out to be your most powerful weapon), so you forge ahead:

$f(4,y) = f(3,f(4,y-1)) = 2^{f(4,y-1)+3}-3.$

At this point, you are strong enough to fight the last boss. You must find a formula for $f(4,y)$ . It looks like $2^{2^{2^{\ldots^2}}}-3$ , with $y+3$ twos in the tower of power. Can you do it? Show me how in the comments. If you need help with writing math in WordPress, search for “latex wordpress” and the internet will teach you how.

In all seriousness (and you will never hear this from me again), you have just completed a journey that few have ever undertaken. As I explained in my previous post, less than 0.001% of the world ever has the privilege of facing a problem like this and coming out on top. Now that you have been inside the belly of the beast, I will let you ponder on this: How far does the rabbit-hole really go?

15 thoughts on “Elementary, my dear Watson”

johnpappas on September 19, 2012 at 5:33 am said:

We have $f(4,y-1)=f(3,f(4,y-2))=2^{f(4,y-2)+3}+3$ .
So $f(4,y)=2^{2^{f(4,y-2)+3}}-3$ .
Therefore, the formula is somethin like $2^{2^{2^{\dots^{2^{f(4,0)+3}}}}}-3$ , where $f(4,0)=f(3,1)=2^4-3=13$ and $\dots$ represent y times raising to the power of two.

Reply ↓
- spiros on September 19, 2012 at 8:14 am said:
  
  Nice John! Why is there y+3 twos in the tower of power?
  
  Reply ↓
  - johnpappas on September 19, 2012 at 11:05 am said:
    
    Maybe because we have one two(the base two) and then $y$ more twos’s and then two more two’s because $2^4=2^{2^{2}}$ ? I am sorry sir if my answer is wrong.
    
    Reply ↓
    - spiros on September 19, 2012 at 11:13 am said:
      
      Almost there John. Why are there $y$ more twos? Why not $y-1$ twos, for example?
      
      Reply ↓
      - johnpappas on September 19, 2012 at 11:44 am said:
        
        You are right sir. If we forget the base two we have $y-1$ twos including the base two of the last power $2^{2^{4}}$ . So what remains is the $2^{2^{2}}$ = three twos. So to sum up, 1 base two, then y-1 twos including the base two of $2^{2^{4}}$ and then three more. Excuse me again if I am wrong.
        
        Reply ↓
        
        spiros on September 19, 2012 at 12:37 pm said:
        
        Can you identify a place in my post where the ingredients for a proof of your statement above lie? Hint: It is close to the second image.
johnpappas on September 20, 2012 at 1:26 am said:

For a proof I was thinking something like
$f(4,y)=f(3,f(4,y-1))= f(2,f(3,f(4,y-1)-1))= f(1, f(2, f(3,(f(4,y-1)-1))-1))$ and the using the fact that the expression $f(1,y+1)$ always equals $y+3$ so recursively we wll have the desired resutl. I might just writing stupid things. Please feel free to reveal the answer.

Reply ↓
- spiros on September 20, 2012 at 10:06 am said:
  
  Look at the paragraph before the second image above. I explain how it is that $f(1,y+1) = f(1,1) + y$ . Can you do the same for $f(4,y)$ ? Hint: Look for a pattern: As the second input decreases by one, how many twos do you add to the tower?
  
  Reply ↓
  - johnpappas on September 22, 2012 at 6:44 am said:
    
    Ok lets see again : $f(4,y+1)=2^{f(4,y)+3}-3= 2^{2^{f(4,y-1)+3}}-3= 2^{2^{2^{f(4,y-2)+3}}}-3 = \dots$ , so whenever y decreases by one in the above expression we add one two(2) to the tower.
    
    Reply ↓
    - spiros on September 22, 2012 at 10:44 am said:
      
      Exactly. So by the time y is zero, you have added y twos to the tower. And the proof is complete as you have mentioned already in a previous comment. Bravo John.
      
      Reply ↓
      - johnpappas on September 22, 2012 at 10:57 am said:
        
        No sir it was all your effort. Please keep posting problems from IMO or other competitions. They are challenging, but with your guidance they are transformed into something almost magical!
        
        Reply ↓
Tyle on February 9, 2013 at 10:06 am said:

Thanks, this problem was awesome! I am proud to say that I did it without looking at your hints – it took me a little more than 15 minutes though!

Reply ↓
- spiros on February 9, 2013 at 6:14 pm said:
  
  Well done Tyle!
  
  Reply ↓
Iman on March 30, 2014 at 7:44 am said:

It was a nice problem really.took me half an hour -without hints-,but even though it took me half an hour to solve, it took me hours to think, whats happening!I mean, how much do we know about this F ?we can as it seems find it for infinite x’s and y’s but this infinite of course doesnt mean we know exactly all!so we can group those (x,y) ‘s we can find F.(perhaps show those discrete points in an x-y plane?) , so what would be those discrete points? like we know F(0,y) for all y.we know F(4,y) for all y.but what else?(what is ALL we know?)

Reply ↓
- Iman on March 30, 2014 at 8:11 am said:
  
  it looks we know it for all natural x and y’s (we can continue to find F(5,y) and so on) but there is a point, to obtain F(k,y) from F(k-1,y) we need to solve a recurrent relation,as we did up to know.but can we solve all the recurrence relations which show up?They seem to get tougher each time!
  
  Reply ↓