Another question on a 2-player game strategy

Question

This is a 2-player game. The game begins with a binary string (leading zeros not ignored).

Each turn, a player can remove a sequence of consecutive and identical digits from the left.

For example, if the current game is $00001110011101$, a player has a choice of removing 1, 2, 3 or 4 zeroes from the left. If the game is $1001011$, the player's only option is to remove the leading 1.

The player who removes the last digit(s) win.

I understand that when the game contains only 0s or 1s, it is a winning position (since the player can simply take all remaining digits). But in general, what is a winning position in this game?

Answer 1

If there are more than one identical digits from the left, the first wins:

1)He can remove all of them

2)He can remove all of them except one then the second have to remove the last.

So he can chose his position(second or first) in the game without first sequence of identical digit. Using your example: 00001110011101 He can remove four zeroes and be the second player in 1110011101-game or he can remove 3 zeroes and be the first one. Then he can obviously win by choosing the position that wins in the new game.

If there is only one identical digit from the left then the players will have only one choice until one of them gets more than one digit and wins.

Answer 2

If the string's first two digits are the same, then the first player has a winning strategy.

They split up the string into "blocks" of digits which are identical. If there are no blocks after the first one, then Player 1 just takes all the digits and wins.

If the next block in the string has at least 2 digits in it, then they remove all but one of the digits in the first block, forcing the second player to remove the remaining digit in that block, which then puts the first player in an essentially equivalent position (with a string beginning with at least two identical digits).

Things get a little trickier if the next block has only one digit in it. Player 1 counts the number of consecutive single digit blocks after the first block. Suppose that there exists a block with at least two digits after this sequence of single digit blocks. If the number of single digit blocks is even, Player 1 proceeds as before, removing all but one of the first multi-digit block, so that they will remove the digit from the first single digit block. This will cause Player 2 to remove the final single digit block, and put Player 1 once again in the situation of having a string beginning with at least two identical digits. If the number of single digit blocks immediately after is instead odd, then Player 1 should remove all of the multi digit block, which will result in the same outcome as before.

If the sequence of blocks is a multi digit block, followed by only single digit blocks, then Player 1 does the opposite, to ensure he takes the final single digit block instead of Player 2.

Of course, if any even number of single digit blocks are placed in front of such a string, then Player 1 will win also (and if its odd, Player 2 will).

In general, to find out who has the winning strategy: count the number of consecutive alternating digits at the front of the string (this being zero if the first two digits are the same). If this number is even, Player 1 has a winning strategy, otherwise Player 2 does.