Game of zeros and ones (Google interview)

Question

I was asked this question a while ago at my Google interview and so far I had no luck finding a good answer to it: This is a 2-player game where you are given a string of zeros and ones. At each turn a player can choose a 1 (or as many 1s next to each other) and change it/them to 0/0s. The player who changes the last 1 (or group of 1s) to 0/0s is the winner of the game.

For example starting with 0101110. The first player has 7 possible moves:

0101110 -> 0001110 (Second player can win)
0101110 -> 0100110 (Second player can win)
0101110 -> 0101010 (Second player can win)
0101110 -> 0101100 (Second player can win)
0101110 -> 0100010 (First player can win)
0101110 -> 0101000 (First player can win)
0101110 -> 0100000 (Second player can win)

The goal is to figure out if there is a winning strategy if you start first. We assume here that both players are good players (meaning that they wont make mistakes!)

Update: This game is slightly different than Nim (https://en.wikipedia.org/wiki/Nim), for Nim the number of piles (or heaps) remain the same at every turn whereas here at every turn you may change the number of piles. For instance if we do 0101110 -> 0101010 initially we have two piles of size 1 and 3 but after the move we will have 3 piles of size 1.

a reasonable player will only make two decisions, take all consecutive ones, or take all ones but one. — Jason Hu
What if you start with 101? The player who moves first loses in this case, since they are forced to change one of the 1s, so the second player can win on their turn. — arshajii
@arshajii yes thats true and in that case there is no winning strategy. "The goal is to figure out if there is a winning strategy if you start first" — sj47sj
It is a nim game, think like this way: group of consecutive 1 is a pile of stones, and different groups means different pile, and there is 2 players... — shole

WhatsUp WhatsUp · Accepted Answer · 2016-03-11T02:56:11

Let nim[n] be the nimber of a sequence of n ones. We then have the following recurrence relation:

nim[n] = mex{nim[i] xor nim[j]: i, j >= 0, i + j < n}

(See Sprague-Grundy theorem for the general theory.)

From this recurrence relation, you can try to calculate the first several terms of the sequence nim, and you will find that it seems nim[n] = n.

Then a proof can be deduced easily, which I shall leave to you.

Thus a sequence of n consecutive ones is actually equivalent to a Nim pile of size n. Now it is easy to find the result of any game.

For example, if we have 0101110, then it is equivalent to two piles of Nim, of size 1 and 3 respectively. Hence the total nimber is equal to 1 xor 3 = 2, which is non-zero, so the first player wins.

As another example, if we have 1110011111000111111, then the total nimber is equal to 3 xor 5 xor 6 = 0, so the first player loses.

EDIT: As to your question about the change of piles, here are some more explanations.

Although the number of piles will change, the key point is the following:

if a status has zero nimber, any valid move must change it to a non-zero nimber status.
if a status has non-zero nimber, then there must exists a valid move, which changes it to a zero nimber status.

Thus for the winner, the strategy is to leave a zero nimber status to his opponent.

Example: let us begin with the sequence 1110011111000111111, which I denote by 3, 5, 6 for short.

If the first player replace the 6 by the sum of 2 and 3, then the second player faces the status 3, 5, 1, 4, which has nimber 3 xor 5 xor 2 xor 3 = 7. In order to keep it zero nimber, the second player replace the 5 by 2, leaving the first player 3, 2, 2, 3, which again has zero nimber.

The procedure continues, until there is no valid move for the first player.

Game of zeros and ones (Google interview)

2 Answers