Two persons play the following game with integers. The initial number is $2011^{2011}$. The players move in turns. Each move consists of subtraction of an integer between $1$ and $2010$ inclusive, or division by $2011$, rounding down to the closest integer when necessary. The player who first obtains a non-positive integer wins. Which player has a winning strategy?
Problem
Source: Baltic Way 2011
Tags: combinatorics proposed, combinatorics
math_explorer
07.11.2011 11:53
The second player wins, by always moving to a positive integer which, when written in base 2011, ends in an odd number of zeroes. We'll call such numbers "safe". Below all digits refer to digits in the base 2011 representation of numbers. There are two things we have to prove to show this is a winning strategy, of course: 1. From any unsafe number $n$ there exists a move to a safe number. (Thus, if the first player can't move to a safe number, the second player always has a response to the first player's moves.) If $n$ ends in more than one zero: since it's unsafe, it ends in an even number of zeroes, so just divide by 2011, which cuts off one zero. If $n$ ends in a nonzero digit $x$: Either subtract $x$ or divide by 2011 and round down. These two moves result in two numbers, one of which ends in an extra zero compared to the other, so exactly one of these is safe. (Or the result is zero and we win.) 2. From any safe number no move to a safe number or to a non-positive integer exists. (Thus, the first player can never move to a safe number or win.) All safe numbers end in zero, so subtracting a number from $1$ to $2010$ results in a number that ends in a nonzero digit, which is unsafe. Dividing by 2011 just cuts off one zero, resulting in a number that ends in an even number of zeroes, which is of course unsafe. Also, all safe numbers are at least $2011$, so no non-positive integers are reachable from them. Finally $2011^{2011}$ ends in $2011$ zeroes, so it's safe and the second player wins.