Monday, July 2, 2018

strategy - A pile of chips involving powers of 2


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

classical mechanics - Moment of a force about a given axis (Torque) - Scalar or vectorial?

I am studying Statics and saw that: The moment of a force about a given axis (or Torque) is defined by the equation: $M_X = (\vec r \times \...