-1
$\begingroup$

Alice and Bob play a game with N non-negative integers.

Players take successive turns, and in each turn, they are allowed to flip active bits from any of the integers in the list.

That is, they pick one (and only one) non-zero integer in the list and flip its as many active bits as desired.

By flipping an active bit of an integer, we mean turning a bit from 1 to 0 in the binary representation of that integer.

As this flipping continues, eventually all numbers in the list become zero.

So the player who ends up turning the last non-zero integer to 0 in the list is the winner (or the player who cannot play on his turn loses).

Given a possible initial configuration, we need to tell if Alice can or cannot beat Bob. Assume that both of them will play optimally (i.e. they do their best in each turn). Also assume that Alice gets the first turn.

Example : Let N=2 and list be [2,9] then in this Alice will win.But say we have N=3 and list be [8,10,290] then in this Bob will move whatever move Alice takes.

So given list of N numbers we need to find winner of this game.

$\endgroup$
  • $\begingroup$ It is misleading to call it 'flipping', because that usually means changing a bit from $1$ to $0$ or from $0$ to $1$. Perhaps 'clearing a non-zero bit' would be better than 'flipping an active bit'. Also, you forgot to stipulate that at least one non-zero bit has to be cleared (otherwise the game will never end). $\endgroup$ – TonyK Sep 13 '14 at 14:00
3
$\begingroup$

This is Nim with each heap having the number of stones as there are $1$ bits in the number. The usual Nim strategy applies-you win by leaving a position where the XOR of the binary expansions of the number of stones in each pile is zero. So $(2,9)$ in your game corresponds to $(1,2)$ in Nim and Alice wins by flipping one bit in $9$. $(8,10,290)$ corresponds to $(1,2,3)$ and is a win for Bob.

$\endgroup$
  • $\begingroup$ @RossMillkan So if XOR is zero then Alice is going to loose .Am i right? $\endgroup$ – user3840069 Sep 13 '14 at 14:09
  • $\begingroup$ That is correct. The proof shows that Alice will then leave a position with nonzero XOR and Bob can restore the XOR to zero. $\endgroup$ – Ross Millikan Sep 13 '14 at 14:10
  • 1
    $\begingroup$ @user3840069: Just to make it clear: first you have to replace each number by the number of 1-bits in it, and then take the XOR. $\endgroup$ – TonyK Sep 13 '14 at 14:10
  • $\begingroup$ user3840069: @TonyK is correct-that is how I went from $(8,10,290)$ to $(1,2,3)$, then $01 \text{ XOR } 10 \text { XOR } 11=0$ $\endgroup$ – Ross Millikan Sep 13 '14 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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