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.
Answer
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)
No comments:
Post a Comment