Imo 2010

From Polymath Wiki
Jump to navigationJump to search

This is the wiki page for the mini-polymath2 project, which seeks solutions to Question 5 of the 2010 International Mathematical Olympiad.

The project will start at 16:00 UTC July 8, and is hosted at the polymath blog. A discussion thread is hosted at Terry Tao's blog.

Rules

This project will follow the usual polymath rules. In particular:

  • Everyone is welcome to participate, though people who have already seen an external solution to the problem should probably refrain from giving spoilers throughout the experiment.
  • This is a team effort, not a race between individuals. Rather than work for extended periods of time in isolation from the rest of the project, the idea is to come up with short observations (or to carry an observation of another participant further) and then report back what one gets to the rest of the team. Partial results or even failures can be worth reporting.
  • Participants are encouraged to update the wiki, or to summarise progress within threads, for the benefit of others.

Threads

Discussion and planning:

Research:

The question

The question to be solved is Question 5 of the 2010 International Mathematical Olympiad:

Problem In each of six boxes [math]\displaystyle{ B_1, B_2, B_3, B_4, B_5, B_6 }[/math] there is initially one coin. There are two types of operation allowed:
Type 1: Choose a nonempty box [math]\displaystyle{ B_j }[/math] with [math]\displaystyle{ 1 \leq j \leq 5 }[/math]. Remove one coin from [math]\displaystyle{ B_j }[/math] and add two coins to [math]\displaystyle{ B_{j+1} }[/math].
Type 2: Choose a nonempty box [math]\displaystyle{ B_k }[/math] with [math]\displaystyle{ 1 \leq k \leq 4 }[/math]. Remove one coin from [math]\displaystyle{ B_k }[/math] and exchange the contents of (possibly empty) boxes [math]\displaystyle{ B_{k+1} }[/math] and [math]\displaystyle{ B_{k+2} }[/math].
Determine whether there is a finite sequence of such operations that results in boxes [math]\displaystyle{ B_1, B_2, B_3, B_4, B_5 }[/math] being empty and box [math]\displaystyle{ B_6 }[/math] containing exactly [math]\displaystyle{ 2010^{2010^{2010}} }[/math] coins. (Note that [math]\displaystyle{ a^{b^c} := a^{(b^c)} }[/math].)

Observations and partial results

  • If the left-most box [math]\displaystyle{ B_1 }[/math] becomes empty, then it cannot ever become non-empty again. Furthermore, the left-most box can never have more than one coin; it can be touched exactly once.
  • Define the worth W of a state to be [math]\displaystyle{ W = B_6 + 2 B_5 + 4 B_4 + 8 B_3 + 16 B_2 + 32 B_1 }[/math]. Then the initial worth is 63, the final desired worth is [math]\displaystyle{ 2010^{2010^{2010}} }[/math], and the Type 1 move does not affect the worth. On the other hand, the Type 2 move increases the worth when [math]\displaystyle{ B_{j+2} - B_{j+1} \geq 4 }[/math].
  • Once one has a large number of coins in one of the first four boxes, say [math]\displaystyle{ B_k }[/math], one can apply the Type 2 move repeatedly to remove coins from [math]\displaystyle{ B_k }[/math] while swapping [math]\displaystyle{ B_{k+1} }[/math] and [math]\displaystyle{ B_{k+2} }[/math] repeatedly. This suggests that it is relatively easy to remove coins from the system; the difficulty is in adding coins to the system.
  • The total number of coins in the system is bounded. Indeed, let [math]\displaystyle{ f(N,\Sigma) }[/math] be the maximum number of coins that one can end up with starting with N boxes with at most [math]\displaystyle{ \Sigma }[/math] coins in them. Thus for instance [math]\displaystyle{ f(1,\Sigma)=\Sigma }[/math]. By considering the times when one touches the left-most box, we can bound [math]\displaystyle{ f(N,\Sigma) }[/math] by at most [math]\displaystyle{ \Sigma }[/math] iterations of the map [math]\displaystyle{ n \mapsto f(N-1,n)+2 }[/math] starting with [math]\displaystyle{ n=\Sigma }[/math]. This gives an Ackermann-type bound on [math]\displaystyle{ f(N,\Sigma) }[/math]. We need f(6,6) to be less than [math]\displaystyle{ 2010^{2010^{2010}} }[/math], but this bound is likely to be too large.

Possible strategies

  • Split the problem into two pieces. Part I: try to show the weaker result that the number of coins in the system can eventually be as large as [math]\displaystyle{ 2010^{2010^{2010}} }[/math]. Part II: Show that once one has a lot of coins, one can move to the final state where [math]\displaystyle{ B_1=\ldots=B_5=0 }[/math] and [math]\displaystyle{ B_6 = 2010^{2010^{2010}} }[/math].
  • Try to show that a quantity such as the worth increases or decreases in a controlled manner as one applies the Type 1 and Type 2 moves.
  • We know that the first box can never contain more than one coin. What can we say about the second box, third box, etc.?
    • There may be a recursive formula for the maximal size of box [math]\displaystyle{ B_j }[/math], possibly requiring one to solve the five-box, four-box, etc. problems first.
  • Work backwards?
  • Try to completely solve the three-box problem (say) first: starting from [math]\displaystyle{ [X,Y,Z] }[/math], what is the most number of coins one can generate?

Compound moves

Here we use Type 1 move [math]\displaystyle{ [a,b] \to [a-1,b+2] }[/math] and the Type 2 move [math]\displaystyle{ [a,b,c] \to [a-1,c,b] }[/math] to create more advanced moves.

  1. We can create the move [math]\displaystyle{ [a,b] \to [0,b+2a] }[/math] from repeated application of Type 1.
  2. We have [math]\displaystyle{ [1,a,b] \to [0,0,a+2b] }[/math] by applying Type 2 once and then Type 1 b times.
    • Or, by using advanced move 1 first, the move [math]\displaystyle{ [1, a, b] \to [1, 0, b+2a] \to [0, b+2a, 0] \to [0, 0, 2b+4a] }[/math].
  3. For [math]\displaystyle{ a \geq 1 }[/math] we have [math]\displaystyle{ [a,0,0] \to [0,2^a,0] }[/math] via [math]\displaystyle{ [a,0,0] \to [a-1,2,0] \to [a-1,0,4] \to [a-2,4,0] \to [a-2,0,8] \to \ldots \to [1, 0, 2^a] \to [0,2^a,0] }[/math].
    • Note that, except for the first move, the coins in the left-most box here are only being used for Type 2 swaps, and otherwise compound move 1 is being applied to the second two boxes.
  4. For [math]\displaystyle{ a,b \geq 1 }[/math] we have [math]\displaystyle{ [a,b,0,0] \to [a-1, 2^b, 0, 0] }[/math]. This follows from the previous compound move together with a Type 2 swap.
  5. For [math]\displaystyle{ a \geq 2 }[/math] we have [math]\displaystyle{ [a,b,0,0] \to [a-2, 2^{b+2}, 0, 0] }[/math], which is valid for [math]\displaystyle{ b=0 }[/math] as well. This follows from applying a Type 1 move to [math]\displaystyle{ [a,b] }[/math] and then applying the previous compound move.

The last two moves seems to be the key to the solutions so far discovered, since it allows one to introduce an exponential at only a linear cost.

Note that we have (and if someone can fix the arrows here and below that would be good)

  1. a [math]\displaystyle{ [n,0] \to [0,2n] }[/math]
  2. a [math]\displaystyle{ [n,0,0] \to [0,2^n,0] \to [0,0,2*2^n ] }[/math]
    • because [math]\displaystyle{ [n,0,0] \to [n-1,2,0] \to [n-1,0,4] \to [n-2,4,0] }[/math] by repeated applications of 1a
  3. a [math]\displaystyle{ [n,0,0,0] \to }[/math][0,2^^n,0,0] [math]\displaystyle{ \to }[/math] [0,0,2^(2^^n),0][math]\displaystyle{ \to }[/math] [0,0,0,2*2^(2^^n)]
    • because [math]\displaystyle{ [n,0,0,0] \to [n-1,2,0,0] \to [n-1,0,2^2,0] \to [n-2,2^2,0,0]\to [n-2,0,2^{2^2},0] \to [n-3,2^{2^2},0,0] }[/math] by repeated applications of 2a, giving [0,2^^n,0,0]
  4. a similarly [math]\displaystyle{ [n,0,0,0,0] \to }[/math][0,2^^^n,0,0,0] etc

World records

To make the second box as big as possible:

  • [math]\displaystyle{ [1,1,1] \mapsto [1,0,3] \mapsto [0,3,0] }[/math] places 3 coins in box 2.

To make the third box as big as possible:

  • [math]\displaystyle{ [1,1,1] \mapsto [0,3,1] \mapsto [0,0,7] }[/math] places 7 coins in box 3. (Here we use advanced move 2).

To make the fourth box as big as possible

  • [math]\displaystyle{ [1,1,1,1] \to [0,3,0,3] \to [0,2,2,3] \to [0,2,0,7] \to [0,1,7,0] \to [0,1,0,14] }[/math] [math]\displaystyle{ \to [0,0,14,0] \to [0,0,0,28] }[/math] gives 28 coins in box 4.

Note that 28 is 2*(2*7), and that the penultimate step has the 14=2*7 as far left as possible.

To make the fifth box as big as possible

[math]\displaystyle{ [1,1,1,1,1] \to [1,0,0,14,0] \to [0,2,0,14,0] \to [0,1,14,0,0] \to [0,1,0,2^{14},0] }[/math][math]\displaystyle{ \to [0,0,2^{14},0,0] \to [0,0,0,2^{2^{14}},0] \to [0,0,0,0,2*2^{2^{14}}] }[/math] with a record of [math]\displaystyle{ 2*2^{2^{14}} }[/math]

The structure is more evident if you write 14=2*7. The process is take 7, multiply by 2, do 2 to power [result], do 2 to power [result], multiply by 2.

The first item on the second row has [math]\displaystyle{ 2^{14} }[/math] as far left as possible and is used ...


To make the sixth box as big as possible

  • Using the move we identified we get to [math]\displaystyle{ \to [1,0,0,2^{14},0,0] \to [0,2,0,2^{14},0,0] \to [0,1,2^{14},0,0,0] }[/math]

Sorry can't see how to do a double Knuth uparrow

  • Then we get [math]\displaystyle{ \to }[/math] [0,1,0,2^^(2^(14)),0,0][math]\displaystyle{ \to }[/math] [0,0,2^^(2^(14)),0,0,0][math]\displaystyle{ \to }[/math] [0,0,0,2^^(2^^(2^(14))),0,0]

[math]\displaystyle{ \to }[/math][0,0,0,0,2^(2^^(2^^(2^(14)))),0] to [0,0,0,0,0,2*2^(2^^(2^^(2^(14))))] The structure Take 7, multiply by two, do 2 to power [result], do 2 double up-arrow [result], do 2 double up-arrow [result], do 2 to power [result], multiply by 2.


TO MAKE THE FINAL BOX AS SMALL AS POSSIBLE WITH ALL OTHERS ZERO

I reckon the answer is:

[1] - last box is 1

[1,1] last box is 3 (only move)

[1,1,1] last box is 3 (do type 2 with first box)

[1,1,1,1] to [1,1,0,3] to [1,0,3,0] to [0,3,0,0] to [0,0,0,0] (type 2 moves exchanging zeros) last box is zero

[1,1,1,1,1] do type 2 with first box (exchanging 1s) to [0,1,1,1,1] then as before [0,0,0,0,0] ... etc

Completed solutions

First solution

Let [math]\displaystyle{ T = 2010^{2010^{2010}} }[/math].

We will be done if we can obtain the configuration [math]\displaystyle{ [0,0,0,T/4,0,0] }[/math], for then we can apply two compound move 1s to get the [math]\displaystyle{ [0,0,0,0,0,T] }[/math].

To get this configuration it is enough to get a configuration [math]\displaystyle{ [0,0,0,X,0,0] }[/math] for some [math]\displaystyle{ X \geq T/4 }[/math], because we can then apply Type 2 moves until the number of coins in the fourth box is reduced to [math]\displaystyle{ T/4 }[/math].

Finally, one can obtain such a configuration using compound move 4. First note that we can get [math]\displaystyle{ [0,0, 140, 0, 0 ,0] }[/math]:

[math]\displaystyle{ [1,1,1,1,1,1] \to [0,2,2,2,2,3] \to [0,2,1,1,8,3] \to [0,2,1,1,0,19] \to [0,1,19,0,0,0] }[/math]
[math]\displaystyle{ \to [0,1,1,36,0,0] \to [0,1,1,1,0,140] \to [0,0,140,0,0,0] }[/math]

From this we get [math]\displaystyle{ [0,0, 139, 2, 0 ,0] }[/math], and then by applying compound move 4 139 times we get [math]\displaystyle{ [0,0, 0, X, 0 ,0] }[/math] for some [math]\displaystyle{ X }[/math] much, much bigger than [math]\displaystyle{ T/4 }[/math], and so we are done.

Second solution

Retrieved from "https://michaelnielsen.org/polymath/index.php?title=Imo_2010&oldid=3220"