Friday, January 18, 2019

mathematics - Halve or diminish, and race to unity!


Alice and Bob are playing a game. In the beginning, the integer 9172016 is written on a blackboard. In a move, a player, can:




  • either decrease the number on the board by 1 (i.e., replace n by n1), or

  • halve the number, and round it up to the next integer if a fraction is obtained (i.e., replace n by n2).


As always, Alice moves first, and then they make moves in turns. The first person to get to 1 wins.



Assuming both players play perfectly, who is going to win the game?



Source: St. Petersburg Math Olympiad, 2001.



Answer




The winner will be



Alice.



More generally,



when the number on the board is even, the player whose turn it is will win.



Proof:




When the number is 2, you can move to 1 and win immediately. Suppose some larger even number is a second-player win (i.e., in this position the player who just played will win with best play). Consider the smallest instance where this happens; call it 2n. If this position is a second-player win then every position you can move to from it must be a first-player win; in particular 2n1 and n are both first-player wins. And since 2n is the smallest even-numbered position that's a second-player win, 2n2 must also be a first-player win. But now the moves available from 2n1 are to 2n2 and to n; those positions are both first-player wins so 2n1 is a second-player win. Contradiction.



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 \...