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.

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

This entry was posted in Real science, The expert's corner by spiros. Bookmark the permalink.

Spyridon Michalakis does research on quantum many-body physics and topological quantum order at Caltech's Institute for Quantum Information and Matter, where he is also the manager for outreach activities.

35 thoughts on “Welcome to the math olympics”

1. Using the notation from the wikipedia article about tetration, I get ${}^{n+3}2-3$. 🙂

• oh, I thought I could use latex…. the answer in words is: a “power tower” of exponents of the number 2, with tower height (n+3), then subtract 3 from that. For your special case, n=2009.

• Use $… $ and substitute … with the word latex, to write tex. Then write the details of how you got your answer 🙂

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

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

4. 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?

• Soonwon, I was going to ask for the last digit of the answer. Steve?

• I think the last digit must be 3, but I have no idea of the next one…

• Apparently, the next digit of the answer is 3, and the whole huge number is …………..33. But I am not sure I have not made a mistake somewhere.

Any confirmation or refutation?

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

• I like this so much.

• And this method seems scalable to certain extent: now it is easy to show that the next figure is 7. In fact,

${}^{m}2 = {2}^{2^{2^{\text{...m times}...^{2}}}} = .........736$ if $m \geq 5$

It might turn out quite possible to calculate a few more decimal digits in the same manner, but enough is enough. 🙂

5. 🙂 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!

• 3,3 and 4? A wild guess.

• 2, 2, 9

• It would be a cool house 🙂

• …and with two more siblings this cool house could even turn into a full house — 2, 2, 9, 9, 9. 🙂

• And it would still be a prime house!

• A house with 13 windows must be a very long or very tall house (given that 13 is prime so more floors wouldn’t help.) But it is all about the sum of the ages having two solutions (2,2,9 and 6,6,1) that is relevant. Great problem 🙂

• 1. First floor always has different number of windows to save space for door(s). So it may be house with three floors and three windows on th first one.
2. Even if both children have age 6, one of them may be older, so information is still not enough.

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

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

8. Pingback: Unsolvable | Quantum Frontiers

9. Wow that was unusual. I just wrote an very long comment but after I clicked submit my comment didn’t appear.
Grrrr… well I’m not writing all that over again. Anyway, just wanted to say excellent blog!