- 2 players A & B are playing a game involving a number n
- Player A makes the first move & both players play alternately.
- In each move the player takes the number n,chooses a number i such that 2^i < n and replaces n with k = n - 2^i iff the number of 1s in the binary representation of k is greater than or equal to the number of 1s in the binary representation of n
- Game ends when no player can make a move, ie there does not exist such an i
For example:
n = 13 = b1101
Only possible i=1
k = n - 2^i = 11 = b1011
Again,only possible i = 2
k = n - 2^i = 7 = b111
Since Player A cant make any more moves, Player B wins
I've deduced that at any step,we can only choose an i,such that there is a 0 at the corresponding position in the binary representation of n.
For Example: if n=1010010,then i can only be {0,2,3,5}.
But I cant move any further.A minimax algorithm isnt exactly striking me.I would appreciate any help.Thanks in advance