Posted on in Mathematics

IMO 2010: Problem 5

Problem 5 of the IMO was definitely the most interesting problem in the contest, although one of the harder ones. A mere 37 people out of 511 managed to solve it completely.

What made it so different was that it did not require any particular knowledge on olympiad math theorems, indeed such knowledge would be useless for this problem. It required only creative insight, and quite a bit of it. Technically it’s a combinatorics problem, but no specific combinatorics experience is needed to solve the problem.

Also this problem was the target for a mini-polymath project organized by Terry Tao, which took about two and a half hours to get from start to solving the problem. The solution I’ll give is mostly based on the polymath solution, although I came up with my own finishing steps which I think is less awkward.

Problem

In each of six boxes B_1,B_2,B_3,B_4,B_5,B_6 there is initially one coin. There are two types of operation allowed:

Type 1: Choose a nonempty box B_j with 1 \leq j \leq 5. Remove one coin from B_j and add two coins to B_{j+1}.

Type 2: Choose a nonempty box B_k with 1 \leq k \leq 4. Remove one coin from B_k and exchange the contents of (possibly empty) boxes B_{k+1} and B_{k+2}.

Determine whether there is a finite sequence of such operations that results in boxes B_1,B_2,B_3,B_4,B_5 being empty and box B_6 containing exactly 2010^{2010^{2010}} coins. (Note that a^{b^c}= a^{(b^c)}.)

Initial observations

It is not entirely obvious how this problem should be approached; thus we will begin by playing with it and jotting down any interesting observations.

We begin with one coin in each box. For convenience, I will express this as

(1,1,1,1,1,1) .

We need to have

(0,0,0,0,0,2010^{2010^{2010}})

Again for convenience, let us substitute

D = 2010^{2010^{2010}}.

Now we can express the two types of moves in our new notation. First, Type 1 moves (we shall call it Move 1):

(a,b) \to (a-1,b+2).

Next, Type 2 moves:

(a,b,c) \to (a-1,c,b).

Notice how applying Move 1 adds one coin to the system as a whole, while Move 2 takes away one coin.

By applying Move 2 over and over, it is easy to remove arbitrarily large amounts of coins from the system (as long as the coins are in the first four boxes).

On the other hand, it isn’t so clear how do add large amounts of coins to the system.

Applying Move 1 adds a coin to the system, so logically adding coins should be done by repeated usage of Move 1.

Given (a,b), applying Move 1 results in (a-1,b+2); applying it again results in (a-2,b+4). We can repeat this as many times as we like, or until the first box is depleted.

This creates a compound move for a pair, executed by applying Move 1 repeatedly:

(a,b) \to (0,b+2a).

What if we apply this on all six boxes? We first get

(0,3,1,1,1,1)

Next we have

(0,0,7,1,1,1);

A few more iterations and we will have:

(0,0,0,0,0,63).

We are far from our target: we have 63 coins and we’re stuck. There doesn’t seem to be any other way to introduce any more coins into the system.

The problem seems hopeless.

Building up a repository of compound moves

We first need a way of getting a large amount of coins into the system. From there is is easy to reduce the coins.

The compound move explained in the previous section is a first step. Let’s call it Compound Move 1:

(a,b) \to (0,b+2a).

The next compound move is less obvious. Suppose that we start with

(a,0,0).

Applying Move 1 gives us

(a-1,2,0)

which, using Compound Move 1, can be used to get

(a-1,0,4).

Now we apply Move 2. Using up a coin to switch the two boxes, we have

(a-2,4,0)

Or equivalently,

(a-2,0,8).

We can repeat this: switching, doubling, switching again, and so on, until the first box is depleted. This gives us

(0,2^a,0).

So here we have Compound Move 2:

(a,0,0) \to (0,2^a,0).

This is a lot better than what we had before. However, it’s still a while towards our goal.

With Compound Move 1, each additional coin in the left most box adds 2 coins to the next box.

But with Compound Move 2, each additional coin doubles the result in the next box.

Now this problem has a Towers of Hanoi feel to it. It turns out that we can take this one step further, which, when examined closely, looks remarkably similar to the previous case.

Suppose we have

(a,0,0,0).

in four consecutive boxes. Applying Move 1:

(a-1,2,0,0).

Applying Compound Move 2 using the last three boxes, we get

(a-1,0,2^2,0).

Now we apply Move 2 and switch the boxes:

(a-2,2^2,0,0).

If we do this again, we get

(a-3,2^{2^2},0,0).

So, repeating this many times until the left box is empty gives us

(0,2^{\cdot^{\cdot^2}},0,0).

No doubt the number we have is sufficiently big now. We will call this move Compound Move 3, which can only be expressed reasonably with Knuth’s up-arrow notation:

(a,0,0,0) \to (0, 2 \uparrow \uparrow a,0,0).

Putting it together

The configuration we want is

(0,0,0,0,0,D)

which is equivalent to

(0,0,0,\frac{D}{4},0,0).

It’s relatively easy to get most of the boxes empty except for the third. From the starting position, Move 1 gives us

(1,1,1,1,0,3)

Applying Move 2 three times gives us

(1,0,3,0,0,0);

Move 1 then gives

(0,0,7,0,0,0).

We invoke Compound Move 3, getting

(0,0,0,2 \uparrow \uparrow 7,0,0).

Finally we can waste coins by consecutively executing Move 2 until we have

(0,0,0,\frac{D}{4},0,0)

And we’re done.

An additional note

It is easy to show, albeit informally, that 2 \uparrow \uparrow 7 > \frac{D}{4}. If we take the binary log (I’ll write it as \log x) of both sides, we have

2 \uparrow \uparrow 6 > 2010^{2010} \cdot \log 2010 - 2.

It’s okay to ‘throw away’ the 2, considering the magnitude of the numbers. Taking the log again:

2 \uparrow \uparrow 5 > 2010 \cdot \log (2010 \cdot \log 2010).

Considering that 2 \uparrow \uparrow 5 = 2^{65536}, and the right hand side evaluates to just a few thousand, it’s fairly safe to say which is bigger.

8 thoughts on “IMO 2010: Problem 5”

  2. Hello trax. Going to answer all of your comments here.

    For geometry, I would definitely recommend Geometry Revisited by Coxeter & Greitzer; although it’s a little bit short of IMO level, it brings you up to date on the more advanced geometry concepts.

    Problem Solving Strategies by Engel is a very good problem book. Past IMO shortlist problems are pretty nice too.

    The IMO is actually for people my age, although I’m not actually on Canada’s IMO team.

    Like

  3. would you be a part of the canada’s imo team for years to come?… by the way, can wikipedia help in learning stuff like on how you solve problem 143 ,giving the proof for the remainder theorem, and all of the problems you posted? Do you plan to post all of the solutions for the imo problems?(problems 1,3,6). Are you specializing in geometry,? because i saw in the imo 2010 problem 4 saying you looked at it in detail because of geometry? and lastly, would you recommend to purchase the AoPS textbooks? (intro to alg.,num theory., coun. and prob. geometry., intermediate algebra, counting an probability, precalculus and calculus) and also the two books?(art of problem solving 1 and 2)…I was planning to purchase it but i thought of purchasing other books because it seems to not cater to the imo’s level. i thought it would be better for me to use the money to purchase other books that are more advanced and suitable for the imo,( which i am surveying on)…Sorry, this is so lenghty, thank you so much i appreciate your reply..:) Take care

    Like

  4. Hi. In my opinion, the internet (with wikipedia, mathworld, khan academy, etc) is not really a substitute for a textbook: unless one already has a knowledge of calculus, he cannot learn it (at least not very well) by reading Wikipedia calculus articles and watching calculus tutorials on youtube. However wikipedia is a good resource for checking some more specific fact, like the proof of the remainder theorem or the like.

    As for the AoPS textbooks, I suppose they’re okay, but not anything special (I’ve only seen the original one though). A list of classic math texts (Spivak, Rudin) can be found here http://math-blog.com/mathematics-books/

    I do like geometry, and I feel it’s my strongest area (of algebra, combinatorics, number theory) though I’m far from an expert at it. I’m wondering if you’re on your country’s IMO team?

    Cheers.

    Like

  5. Oh, I see, thank you very much.

    Well, i’ve just discovered IMO this year, and right now i have to go through two more steps (camp) before making the team.

    I take it you are going to be entering the IMO next year?

    Like

  6. I’m in a similar situation. I recently discovered the local CMS math club – I’m a junior high student- and have been loving it. I still have a long way to go, though, especially in geometry.

    Like

  7. Excellent explanation to this problem. I find a lot of the official IMO solutions are very difficult to follow, but this was done at a level I (or just about any person) could understand. Great job!

    Like

Leave a comment