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

Popular posts from this blog

1995 IMO #2

Inequality problem I made