# Difference between revisions of "2010 IMO Problems/Problem 5"

(Created page with '== Problem == Each of the six boxes <math>B_1</math>, <math>B_2</math>, <math>B_3</math>, <math>B_4</math>, <math>B_5</math>, <math>B_6</math> initially contains one coin. The f…') |
m |
||

Line 10: | Line 10: | ||

''Author: Unknown currently'' | ''Author: Unknown currently'' | ||

+ | |||

+ | == Solution == | ||

+ | |||

+ | Let the notation <math>[a_1,a_2,a_3,a_4,a_5,a_6]</math> be the configuration in which the <math>x</math>-th box has <math>a_x</math> coin, | ||

+ | |||

+ | Let <math>T=2010^{2010^{2010}}</math>. | ||

+ | |||

+ | <br/> | ||

+ | |||

+ | Our starting configuration is <math>[1,1,1,1,1,1]</math> | ||

+ | |||

+ | <br /> | ||

+ | |||

+ | We need these compound moves: | ||

+ | |||

+ | Compound move 1: <math>[a,0]\rightarrow[0,2a]</math>, this is just repeated type 1 move on all <math>a</math> coins. | ||

+ | |||

+ | Compound move 2: <math>[a,0,0]\rightarrow[0,2^a,0]</math>, apply type 1 move on 1 of the coin to get <math>[a-1,2,0]</math>, then apply compound move 1 to the 2 coins to get <math>[a-1,0,2^2]</math>, apply type 2 move and get <math>[a-2,2^2,0]</math>, and repeat compound move 1 and type 2 move until <math>[0,2^a,0]</math> is achieve. | ||

+ | |||

+ | Compound move 3: <math>[a,b,0,0]\rightarrow[a-1,2^b,0,0]</math>, apply compound move 2 to obtain <math>[a,0,2^b,0]</math> and use type 2 move to get <math>[a-1,2^b,0,0]</math> | ||

+ | |||

+ | Compound move 4: <math>[a,0,0,0]\rightarrow[0,2^{2^{.^{.^{.^2}}}},0,0]</math> with <math>a</math> <math>2</math>'s. Apply compound move 3 <math>a</math> times. | ||

+ | |||

+ | Compound move 5: <math>[a,0,0]\rightarrow[b,0,0]</math> with <math>a>b</math>, use type 2 move <math>(a-b)</math> times. | ||

+ | <br/><br/> | ||

+ | |||

+ | Let's follow this move: | ||

+ | |||

+ | <math>[1,1,1,1,1,1] \rightarrow[0,3,1,1,1,1] \rightarrow[0,2,3,1,1,1]\rightarrow[0,2,1,5,1,1]\rightarrow[0,2,1,1,9,1]\rightarrow[0,2,1,1,0,19]\rightarrow[0,1,19,0,0,0]</math> | ||

+ | |||

+ | |||

+ | Using Compound move 1, 4 and 5, We can obtain: | ||

+ | |||

+ | <math>[0,1,19,0,0,0]\rightarrow[0,1,0,X,0,0]\rightarrow[0,0,X,0,0,0]\rightarrow[0,0,0,Y,0,0]\rightarrow[0,0,0,T/4,0,0]\rightarrow[0,0,0,0,T/2,0]\rightarrow[0,0,0,0,0,T]</math> | ||

+ | |||

+ | , where <math>X, Y = 2^{2^{.^{.^{.^2}}}}</math> where X has <math>19</math> 2's and Y has <math>X</math> 2's, and <math>Y</math> is clearly bigger then <math>T/4</math> |

## Revision as of 00:34, 24 October 2010

## Problem

Each of the six boxes , , , , , initially contains one coin. The following operations are allowed

Type 1) Choose a non-empty box , , remove one coin from and add two coins to ;

Type 2) Choose a non-empty box , , remove one coin from and swap the contents (maybe empty) of the boxes and .

Determine if there exists a finite sequence of operations of the allowed types, such that the five boxes , , , , become empty, while box contains exactly coins.

*Author: Unknown currently*

## Solution

Let the notation be the configuration in which the -th box has coin,

Let .

Our starting configuration is

We need these compound moves:

Compound move 1: , this is just repeated type 1 move on all coins.

Compound move 2: , apply type 1 move on 1 of the coin to get , then apply compound move 1 to the 2 coins to get , apply type 2 move and get , and repeat compound move 1 and type 2 move until is achieve.

Compound move 3: , apply compound move 2 to obtain and use type 2 move to get

Compound move 4: with 's. Apply compound move 3 times.

Compound move 5: with , use type 2 move times.

Let's follow this move:

Using Compound move 1, 4 and 5, We can obtain:

, where where X has 2's and Y has 2's, and is clearly bigger then