2
$\begingroup$
  • 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

1 Answers 1

1

It’s a disguised version of Nim. Each block of consecutive $0$’s in the binary representation of $n$ is a pile. For example, from $10000_2$ you can subtract $8$ to get $1000_2$; $4$ to get $1100_2$; $2$ to get $111_2$; or $1$ to get $1111_2$. These moves correspond to reducing a pile of $4$ stones to $3$, $2$, $1$, or $0$ stones, respectively. I’ll leave it to you to fill in the details. You probably already know the strategy for Nim.

(This is a cute variant; I’d not seen it before.)

  • 0
    It seems that every position has value $0$, $*$, or $*2$.2012-09-25