Quantum Frontiers

Welcome to the math olympics

September 6, 2012 5:22 pm

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

Posted by spiros

Categories: Real science, The expert's corner

Tags:

« Older Newer »

35 Responses to “Welcome to the math olympics”

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

By sflammia on September 6, 2012 at 6:06 pm
1. 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.
  
  By sflammia on September 6, 2012 at 6:08 pm
  1. Use $… $\text{[math]}$ $ and substitute … with the word latex, to write tex. Then write the details of how you got your answer 🙂
    
    By spiros on September 6, 2012 at 7:21 pm
  2. Dr. Flammia’s answer: ${}^{n+3}2-3$
    
    By Soonwon on September 6, 2012 at 9:21 pm
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))))))

By argosvanburen on September 6, 2012 at 7:20 pm
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
  
  By argosvanburen on September 6, 2012 at 7:31 pm
  1. 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
    
    By argosvanburen on September 6, 2012 at 7:47 pm
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!).

By Soonwon on September 6, 2012 at 9:05 pm
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?

By Soonwon on September 6, 2012 at 9:07 pm
1. Soonwon, I was going to ask for the last digit of the answer. Steve?
  
  By spiros on September 6, 2012 at 11:50 pm
  1. I can give you the answer with 25% chance to be right.
    
    By Soonwon on September 7, 2012 at 12:02 pm
2. I think the last digit must be 3, but I have no idea of the next one…
  
  By Konstantin Krayn on September 7, 2012 at 10:51 am
  1. 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?
    
    By Konstantin Krayn on September 7, 2012 at 12:10 pm
    1. 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.
      
      By spiros on September 7, 2012 at 12:25 pm
    2. 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$ .
      
      By Lord Sidious on September 8, 2012 at 12:23 pm
      1. 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.
        
        By spiros on September 10, 2012 at 12:01 pm
      2. 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.
        
        By Konstantin Krayn on September 11, 2012 at 3:02 am
        
        I like this so much.
        
        By spiros on September 11, 2012 at 7:33 am
        
        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. 🙂
        
        By Konstantin Krayn on September 11, 2012 at 8:40 am
🙂 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!

By Alexey Gorshkov on September 7, 2012 at 2:23 am
1. 3,3 and 4? A wild guess.
  
  By spiros on September 7, 2012 at 12:31 pm
2. 2, 2, 9
  
  By Konstantin Krayn on September 7, 2012 at 12:46 pm
  1. It would be a cool house 🙂
    
    By spiros on September 7, 2012 at 1:09 pm
    1. …and with two more siblings this cool house could even turn into a full house — 2, 2, 9, 9, 9. 🙂
      
      By Konstantin Krayn on September 7, 2012 at 1:21 pm
      1. And it would still be a prime house!
        
        By spiros on September 7, 2012 at 1:29 pm
        
        Konstantin is right – sorry, Spiros 🙂
        
        By Alexey Gorshkov on September 8, 2012 at 12:38 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 🙂
        
        By spiros on September 8, 2012 at 1:11 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.
        
        By Alexander on September 14, 2012 at 2:26 am
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.

By Filip on September 7, 2012 at 8:44 am
[…] Link. Neat slice of a life. by jgordon on September 8, 2012 • Permalink Posted in share Tagged s […]

By » Personal story of a mathematical wizard. Gordon's shares on September 8, 2012 at 7:15 pm
[…] Post navigation ← Previous […]

By Elementary, my dear Watson | Quantum Frontiers on September 11, 2012 at 12:04 am
[…] одобрил градостроительный совет. Памятник … 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 […]

By HoT NeWs » Прайм крайн on January 16, 2013 at 5:54 pm
[…] 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 […]

By Unsolvable | Quantum Frontiers on January 23, 2013 at 5:56 pm
[…] 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 […]

By An unlikely love affair | Quantum Frontiers on April 16, 2013 at 1:26 pm
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!

By Sheena on September 12, 2014 at 12:02 am