Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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 23:34, 23 October 2010

Problem

Each of the six boxes $B_1$, $B_2$, $B_3$, $B_4$, $B_5$, $B_6$ initially contains one coin. The following operations are allowed

Type 1) Choose a non-empty box $B_j$, $1\leq j \leq 5$, remove one coin from $B_j$ and add two coins to $B_{j+1}$;

Type 2) Choose a non-empty box $B_k$, $1\leq k \leq 4$, remove one coin from $B_k$ and swap the contents (maybe empty) of the boxes $B_{k+1}$ and $B_{k+2}$.

Determine if there exists a finite sequence of operations of the allowed types, such that the five boxes $B_1$, $B_2$, $B_3$, $B_4$, $B_5$ become empty, while box $B_6$ contains exactly $2010^{2010^{2010}}$ coins.

Author: Unknown currently

Solution

Let the notation $[a_1,a_2,a_3,a_4,a_5,a_6]$ be the configuration in which the $x$-th box has $a_x$ coin,

Let $T=2010^{2010^{2010}}$.


Our starting configuration is $[1,1,1,1,1,1]$ 


We need these compound moves:

Compound move 1: $[a,0]\rightarrow[0,2a]$, this is just repeated type 1 move on all $a$ coins.

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

Compound move 3: $[a,b,0,0]\rightarrow[a-1,2^b,0,0]$, apply compound move 2 to obtain $[a,0,2^b,0]$ and use type 2 move to get $[a-1,2^b,0,0]$

Compound move 4: $[a,0,0,0]\rightarrow[0,2^{2^{.^{.^{.^2}}}},0,0]$ with $a$ $2$'s. Apply compound move 3 $a$ times.

Compound move 5: $[a,0,0]\rightarrow[b,0,0]$ with $a>b$, use type 2 move $(a-b)$ times.

Let's follow this move: 

$[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]$


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

$[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]$

, where $X, Y = 2^{2^{.^{.^{.^2}}}}$ where X has $19$ 2's and Y has $X$ 2's, and $Y$ is clearly bigger then $T/4$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2010_IMO_Problems/Problem_5&oldid=35950"