Institute for Quantum Information and Matter, a National Science Foundation Physics Frontiers Center

# 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 \$latex f(0,y) = y+1, , f(x+1,0) = f(x,1)\$ and \$latex f(x+1,y+1) = f(x, f(x+1,y))\$, for all non-negative integers \$latex x,y\$, find \$latex f(4,2009)\$.

2017-01-13T10:06:04+00:00 September 6th, 2012|Real science, The expert's corner|35 Comments

1. sflammia September 6, 2012 at 6:06 pm - Reply

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

• sflammia September 6, 2012 at 6:08 pm - Reply

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.

• spiros September 6, 2012 at 7:21 pm - Reply

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

• Soonwon September 6, 2012 at 9:21 pm - Reply

Dr. Flammia’s answer: \$latex {}^{n+3}2-3 \$

2. argosvanburen September 6, 2012 at 7:20 pm - Reply

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

• argosvanburen September 6, 2012 at 7:31 pm - Reply

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

• argosvanburen September 6, 2012 at 7:47 pm - Reply

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. Soonwon September 6, 2012 at 9:05 pm - Reply

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. Soonwon September 6, 2012 at 9:07 pm - Reply

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?

• spiros September 6, 2012 at 11:50 pm - Reply

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

• Soonwon September 7, 2012 at 12:02 pm - Reply

I can give you the answer with 25% chance to be right.

• Konstantin Krayn September 7, 2012 at 10:51 am - Reply

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

• Konstantin Krayn September 7, 2012 at 12:10 pm - Reply

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?

• spiros September 7, 2012 at 12:25 pm - Reply

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.

• Lord Sidious September 8, 2012 at 12:23 pm - Reply

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

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

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

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

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

• spiros September 10, 2012 at 12:01 pm

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.

• Konstantin Krayn September 11, 2012 at 3:02 am

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 \$latex 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, \$latex N = 10A + 6 = 4B\$, hence \$latex 5A + 3 = 2B\$, and A has to be odd: \$latex A = 2C + 1\$. Then \$latex N = 20C + 16\$.

Now to \$latex 2^{N} = 2^{16} times 2^{20C}\$. Obviously, \$latex 2^{16} = 65536\$ ends with 36. Also, \$latex 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, \$latex 2^{20C} = …76 times …76 times … times …76\$ ends with 76.

So, our “power tower” \$latex 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.

• spiros September 11, 2012 at 7:33 am

I like this so much.

• Konstantin Krayn September 11, 2012 at 8:40 am

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

\$latex {}^{m}2 = {2}^{2^{2^{text{…m times}…^{2}}}} = ………736\$ if \$latex 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. Alexey Gorshkov September 7, 2012 at 2:23 am - Reply

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

• spiros September 7, 2012 at 12:31 pm - Reply

3,3 and 4? A wild guess.

• Konstantin Krayn September 7, 2012 at 12:46 pm - Reply

2, 2, 9

• spiros September 7, 2012 at 1:09 pm - Reply

It would be a cool house 🙂

• Konstantin Krayn September 7, 2012 at 1:21 pm - Reply

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

• spiros September 7, 2012 at 1:29 pm

And it would still be a prime house!

• Alexey Gorshkov September 8, 2012 at 12:38 am

Konstantin is right – sorry, Spiros 🙂

• spiros September 8, 2012 at 1:11 am

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 🙂

• Alexander September 14, 2012 at 2:26 am

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. Filip September 7, 2012 at 8:44 am - Reply

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. […] Link. Neat slice of a life. by jgordon on September 8, 2012  •  Permalink Posted in share Tagged s […]

8. […] Post navigation ← Previous […]

9. HoT NeWs » Прайм крайн January 16, 2013 at 5:54 pm - Reply

[…] одобрил градостроительный совет. Памятник … Welcome to the math olympics | Quantum Frontiers Konstantin Krayn on September 7, 2012 at 12:10 pm said: Apparently, the next digit of the answer is […]

10. Unsolvable | Quantum Frontiers January 23, 2013 at 5:56 pm - Reply

[…] problem that I soon realized was close to being unsolvable. The setting was the Banquet for the 38th International Math Olympiad. I was 17 and there was delicious, free food in front of me, so it was pretty impossible to get my […]

11. […] during class. And then the miracle happened again. I aced the class. I have already discussed my superpower of super-stubbornness, but this was different. I actually had to learn stuff in order to do well in advanced quantum […]

12. Sheena September 12, 2014 at 12:02 am - Reply

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!