Ann and Bob play alternately on a pile of chips. On each play, any number of chips, which is a power of 2 (including 1=$2^0$), can be removed from the pile. Obviously the number of chips to be removed cannot be higher than the number of chips on the current pile. The person, who removes the last chip is the winner. There are 452 chips on the pile. Ann starts. Determine a winning strategy for one of the players.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Ann wins. The strategy is for Ann to remove the number of chips to a multiple of 3. As powers of 2 cover both 1 and 2 modulo 3, this is always possible when the number Ann receives is not a multiple of 3. Conversely, Bob will never be able to do this. Because 0 is a multiple of 3 and the number of chips is a strictly decreasing monovariant, Bob cannot win, and thus Ann will win.
Code to find the pattern: https://ideone.com/O5S4Qu (The third number printed out on each line is the winning move if the player to move is in a winning position)
$\begingroup$
$\endgroup$
1
We have a winning strategy for:
Ann
The first move is:
Take 2 chips, leaving Bob with a multiple of 3. No power of 2 is a multiple of 3, so he cannot win immediately. Likewise, he cannot leave Ann with a multiple of 3, since he would have to subtract a multiple of 3 to do so. Then on Ann's next move, she simply takes 1 or 2 chips, whichever would leave Bob with another multiple of 3. This must be possible, since any number that isn't a multiple of 3 must be at most 2 more than a multiple of 3. Since Bob can never win, and Ann can always take at least one chip, eventually Ann must win with this strategy.
-
$\begingroup$ interesting ...any other way to solve this ? I am trying to find all possible ways to approach this question. $\endgroup$ Nov 23, 2021 at 19:18