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

2010 IMO Problems/Problem 5

Revision as of 23:34, 23 October 2010 by Moplam (talk | contribs)

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"