Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  • 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

share|improve this question
add comment

1 Answer 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.)

share|improve this answer
    
This doesn't seem right, since the removal of zeroes from one block will create new zeroes in the next block to the left. The value of $1010_2$, for instance, is $*$, not $0$, even there are two equal "piles" of zeroes in that number. –  Théophile Sep 24 '12 at 23:50
    
@Théophile: You’re right: I was concentrating so much on the case of adjacent $1$’s that I forgot that the piles get amalgamated in the basic case! –  Brian M. Scott Sep 25 '12 at 0:03
    
I’ll revise this when I get back. –  Brian M. Scott Sep 25 '12 at 0:10
    
It seems that every position has value $0$, $*$, or $*2$. –  Théophile Sep 25 '12 at 0:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.