2009 IMO SL #C1

-

Problem: Consider $2009$ cards, each having one gold side and one black side, lying on parallel on a long table. Initially all cards show their gold sides. Two player, standing by the same long side of the table, play a game with alternating moves. Each move consists of choosing a block of $50$ consecutive cards, the leftmost of which is showing gold, and turning them all over, so those which showed gold now show black and vice versa. The last player who can make a legal move wins. (a) Does the game necessarily end? (b) Does there exist a winning strategy for the starting player?



Solution:

 (a) Consider the row of cards to be a binary number, with a card showing its gold side representing a $1$ and a card showing its black side representing a $0$. We see that since the leftmost card of every move has to be gold, applying a move always decreases our number. Therefore, since we clearly can't go to negative numbers, the game can only have finitely many moves, and therefore does eventually end. $\square$ 

(b) Label the bits $1, 2, \cdots, 2009$ from right to left. Now, consider the bits that have a label that is divisible by $50$ (i.e. bits $50, 100, \cdots, 2000$). There are $40$ such bits, and we see that each one needs to be toggled an odd number of times for the game to end. However, the sum of $40$ odd numbers will be even, so the game must end in an even number of moves. This implies that player $2$ must make the last move of the game, so player $1$ does $\textit{not}$ have a winning strategy. $\square$

Comments

Post a Comment

Popular posts from this blog

1995 IMO #2

-
 Let $ a$, $ b$, $ c$ be positive real numbers such that $ abc = 1$. Prove that \[ \frac {1}{a^{3}\left(b + c\right)} + \frac {1}{b^{3}\left(c + a\right)} + \frac {1}{c^{3}\left(a + b\right)}\geq \frac {3}{2}. \]
Read more

2014 IMO SL #C2

-
  Problem : We have $2^m$ sheets of paper, with the number $1$ written on each of them. We perform the following operation. In every step we choose two distinct sheets; if the numbers on the two sheets are $a$ and $b$, then we erase these numbers and write the number $a + b$ on both sheets. Prove that after $m2^{m -1}$ steps, the sum of the numbers on all the sheets is at least $4^m$ .
Read more

2015 IMO SL #A1

-
 Suppose that a sequence $a_1,a_2,\ldots$ of positive real numbers satisfies\[a_{k+1}\geq\frac{ka_k}{a_k^2+(k-1)}\]for every positive integer $k$. Prove that $a_1+a_2+\ldots+a_n\geq n$ for every $n\geq2$.
Read more