Welcome to the math olympics

It was a beautiful day in the Winter of 1994. I had slept in because it was Saturday, but my older brother, Nikos, was not so lucky. He had just come back from a regional math competition named after the Greek philosopher Θαλής (Thales of Miletus) and he did not look happy. I asked him how he did, but he did not answer; he just reached into his backpack and took out the paper that contained the problems from the competition. Looking back, what I did next defines much of how I approach life since that day: I took the paper and started solving the problems one after the other until I was done. It took me three days – the competition lasted three hours.

The next year, I was old enough to compete in the first round of the Greek Math Olympiad and I convinced a bunch of my friends from school (remember the cool nerds from Geniuses wanted?) to wake up early on a Saturday and go test our mettle against the rest of the Greek population still in school (though university students were too old to compete). You know how people talk about the 1% these days… To make it into the next round you had to be in the 1% of something that none of us knew how to define back then. After all, we were all equally scared of the old guys with the formal suits and the strict faces holding the exam papers. How was I, or any one of my friends from school, different from all the other kids taking the exam throughout the country that day? Did we have a special upbringing? Did our parents answer math questions for fun? At the moment I received the paper with the 4 problems on it, I immediately hoped I had a special upbringing. That my dad was not a high-school dropout and my mom had studied math in college, instead of political science. Damn. These problems looked hard. But I knew what I was supposed to do. So I started solving them, one after the other. Unfortunately, the time ran out after 3 hours and I had only solved 2 and 1/2 problems by then. But after I got home, I said hi to my mom, ate a sandwich and went into my room. I stayed there until I had finished the other 1 and 1/2 problems. Emerging victorious from my room that night, I made another ham-and-cheese sandwich and added extra ketchup to reward myself.

Thundercats, not a school mascot.

A month later, I learned that I had made it into the 1%. And four months later, into the 0.01% that went on to the final round named after the famous Greek nudist, Αρχιμήδης (Archimedes of Syracuse). My dad, mom, brothers, classmates and, especially, teachers, were incredulous. But that was nothing compared to how I felt. They thought I was a lazy bum, but I knew it for certain. How did I get to reach the finals and make it into the top 20 of all Greek high-schoolers? I was not even in high-school yet! Who knows… All I know is that I would stay up past 3 a.m. on Tuesday nights to solve problems from Crux Mathematicorum with Mathematical Mayhem, when everyone else was fast asleep. And I wouldn’t stay up that late even if my favorite cartoon (Thundercats) was on TV at that time (which is a bit ironic, since my parents thought I was watching TV all night and so considered it appropriate to wake me up using buckets of water).

I didn’t solve these math problems because I was planning to be a mathematician. I disliked math class in school as much as (probably more than) my classmates. But this was different. These problems did not appear at the end of a chapter full of dry equations and ready-made formulas. The problems on Crux Mathematicorum were dancing in the middle of pages surrounded by other problems vying for attention. Any progress I made was solely due to stubbornness. But then, I started unlocking my superpowers one-by-one. And I started seeing patterns, not only mathematical patterns, but patterns in my own thoughts and my own temper when confronting impossible problems. Which came in really handy later in life when I was asked to solve a much harder problem (An intellectual tornado).

So now that you are all primed, here is a problem to keep you occupied for a few hours, or days…

Problem 1: 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).

34 thoughts on “Welcome to the math olympics

  1. Don’t see how it converges.
    Using
    f(4,2009) = f(3,f(4,2008))
    f(3,f(3,f(3,……f(3,0)
    f(3,0) = f(2,1) = f(2,f(2,0)) = f(2,f(1,1)) = f(2,f(1,f(1,0))) = f(2,f(1,f(1,f(0,1))))
    Lowest level is a recursive loop
    f(1,f(0,1))
    f(1,2) = f(1,f(1,1)) = f(1,f(1,f(1,0))) =
    f(1,f(1,f(1,f(0,1)))
    f(1,f(1,f(1,2)))
    f(1,f(1,f(1,f(1,f(1,f(0,1)))))
    f(1,f(1,f(1,f(1,f(1,2))))
    f(1,f(1,f(1,f(1,f(1,f(1,f(1,f(0,1))))))

    • f(0,y) = y wouldn’t be in the recursive loop but it also doesn’t evaluate to anything
      f(1,f(0,1)) = f(1,1) = f(1,f(1,0)) = f(1,f(0,1))
      f(0,y+1) =y isn’t in the recursive loop but it just evaluates to 0
      f(1,f(0,1)) = f(1,0) = f(0,1) = 0

      • f(3,0) = f(2,1) = f(2,f(2,0)) = f(2,f(1,1)) = f(2,f(1,f(1,0))) = f(2,f(1,f(0,1)))
        last equals on that line had an extra nest

  2. Alright.
    I was coming back from a gym and read your nostalgic story on my smartphone while walking.
    I enjoyed the reading a lot, mostly because I had pretty much the same experiences with physics competitions in Korea. And, of course, your challenge has been accepted!

    My first reaction was like this: “Alright. let’s grab a pen and a piece of paper. I should be able to find the anser in like 5 or 10mins, and then I would take a shower..” However, after 20 mins or so, no hope. I got serious about the problem, sat in front of a desk, rewrote the problem statement again and started from the beginning.

    Honestly, from that poing it took (a very slightly) more than 20mins to find the answer, which agrees with Steve’s one. Even though I am dry and smells nasty, I feel very good because now I know the answer! and more importantly because this problem reminded me of the time when I was spending nights to solve physics problems. It seems like I have not changed so much from since that time. :-)

    PS. For those of you who are still struggling, let me give you a hint. Don’t try to solve the problem at once, the structure of the two dimensional function is rather complex than to be called as a two dimensional nice looking function. Begin with small numbers and find the “pattern” just as Sprios (and probably all of us) has been doing since he was a little kid (and probably even now for our research!).

  3. By the way, the answer is very very very big number.
    Just out of curiosity, is there anyone who can write the last 4 digits of the answer?

        • Hi Konstantin. Just landed back in the good ol’ US of A. The last digit is 3 (easy to figure that out) and I am sure that you got 33 right, though I can’t confirm it in my head.

        • I define p_n = 2^{p_{n-1}}, p_1 = 2. To find the last two digits we compute p_{2009} \pmod{4} and p_{2009} \pmod{25}. It’s easy to see that p_{2009} \equiv 0 \pmod{4}. Now, p_{2009} \equiv 2^{p_{2008}} \pmod{25}.

          However, 2^{\phi(25)} \equiv 1 \pmod{25}, where \phi is the Euler totient function \phi(25) = 25 \left(1 - \frac 1 5\right) = 20. Therefore 2^{p_{2008}} \equiv 2^{p_{2008} \pmod{20}}  \pmod{25}. So now we need to compute p_{2008} \pmod{20}.

          We proceed as before, and we compute p_{2008} \pmod{4} and p_{2008} \pmod{5}. The first is easy, p_{2008} \equiv 0 \pmod{4}. For the second we have p_{2008} \equiv 2^{p_{2007}} \pmod{5} \equiv 2^{p_{2007} \pmod{\phi(5)}} \pmod{5}. Since \phi(5) = 5 \left(1-\frac 1 5\right) = 4. Since p_{2007} \equiv 0 \pmod{4}, we get that p_{2008} \equiv 2^0 \pmod{5} \equiv 1 \pmod{5}.

          So, we have that p_{2008} \equiv 0 \pmod{4} and p_{2008} \equiv 1 \pmod{5}. This implies that p_{2008} \equiv 16 \pmod{20}. Going back, we obtain that p_{2009} \equiv 2^{16} \pmod{25} \equiv 11 \pmod{25}. So, we have p_{2009} \equiv 11 \pmod{25} and p_{2009} \equiv 0 \pmod{4}. From here we find the only solution is p_{2009} \equiv 36 \pmod{100}.

          Since we need to subtract 3 to obtain the answer of this problem, we find that the last two digits are 33.

          • Excellent solution Lord Sidious! The power of the dark side is indeed great. To post in latex, you only need to append “latex” after the opening $. For example, $latex …latex code… and then close the dollar sign.

          • Lord Sidious, thank you for your calculation that yields “…33″ answer in a professional “powerful arithmetic” language. My amateur solution does not involve Euler’s totient function, but it is basically about the same ideas, I think.

            The first simple observation is that consecutive powers of 2, i.e. 2, 4, 8, 16, 32, 64, 128, 256, … in decimal notation end with 2, 4, 8, 6, 2, 4, 8, 6, …, respectively, which is a cycle with four members. Therefore, the last digit of any power of 2 depends on the remainder of the index mod 4. In our problem, the number in question is 2 to some great positive integer power N, where index N is itself a great power of 2, and it is certainly divided by 4, hence the last digit of 2^{N} is 6.

            Now to the second decimal digit. It does not take long to figure out that N is not only divided by 4, as we have already seeen, but also ends with 6 (because N is a power of 2 whose own index is divided by 4). Therefore, N = 10A + 6 = 4B, hence 5A + 3 = 2B, and A has to be odd: A = 2C + 1. Then N = 20C + 16.

            Now to 2^{N} = 2^{16} \times 2^{20C}. Obviously, 2^{16} = 65536 ends with 36. Also, 2^{20} = 1048576 ends with 76. The key observation is that the product of two numbers each ending with 76 must also end with 76 — it could easily be seen by calculating the product using the standard school multiplication method (in Russia it is called “stolbikom”, which means that you write multiplicands one under another). Therefore, 2^{20C} = ...76 \times ...76 \times ... \times ...76 ends with 76.

            So, our “power tower” 2^{N} has been shown equal to the product of two numbers, one ending with 36 and the other ending with 76. Such a product must end with 36 (again, “stolbikom”multiplication method helps to see why). Subtracting 3, we get a number that ends with 33.

  4. :) The following problem was given to some 5th graders in Russia this week. The answer is unique.

    Two friends meet on the street. One asks the other
    – you have kids?
    – yup, I have three kids.
    – how old are they?
    – if you multiply their ages, you get 36.
    – this is not enough information – tell me more!
    – if you add their ages, you get the same number as number of windows you can see in this house.
    – still not enough information! tell me more!
    – the oldest child is a redhead.
    – now I get it!

  5. Nice story Spiros.
    I used to go every year to math competitions in my country, starting from the 4th grade until I finished the elementary school (those were for the elementary school pupils). I was always among the first 3 at school, and every year I managed to get through the first 2 rounds and compete in regional (after that was the national competition). This is not some big success at all, but what I regret most is that I was never preparing for the competition and never doing some problems at home. I actually never studied math until high school, all I heard in class was enough. Although I never had problems with math (and I had it a lot in high school and at the faculty later), I really regret for not being more into it when I was young. I don’t know, I just did not find it interesting back then as I find it today.

  6. Pingback: » Personal story of a mathematical wizard. Gordon's shares

  7. Pingback: Elementary, my dear Watson | Quantum Frontiers

  8. Pingback: HoT NeWs » Прайм крайн

  9. Pingback: Unsolvable | Quantum Frontiers

  10. Pingback: An unlikely love affair | Quantum Frontiers

Your thoughts here.

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