5. In the country of Cuccagna, the following solitaire game is played. You start with a finite string of zeros and ones, and the following moves are allowed:

(i) delete two consecutive ones;

(ii) delete three consecutive zeros;
(iii) if the substring 01 appears within the string, this substring can be replaced with 100.

Moves (i), (ii), and (iii) must be made one at a time and in sequence. You win if you manage to reduce the string to one consisting of two digits or fewer.

(For example, starting from 0101, you can win by first using move (iii) on the last two digits, resulting in 01100, then playing move (i) on the two ones in this string, and finally move (ii) on the three zeros left: this results in the empty string.)

How many of the 1024 possible ten-digit strings are those from which it is not possible to win the solitaire?
Solution: I prove that the only string of ten digits from which it is not possible to win the solitaire is 1111100000 (five ones followed by five zeros).

Given a string, I consider these two quantities:

- the number of ones,
- the total weight of the zeros, where a zero with $i$ ones to its right weighs $2^{i}$. (For example, each of the zeros in the string 001 weighs 2.)

Move (iii) leaves both quantities unchanged, because it does not change the number of ones and replaces a zero with two that weigh, each, half as much. I therefore assign to each string a type represented by a pair of numbers: the first is the remainder of the division by 2 of the number of ones, the second is the remainder of the division by 3 of the weight of the zeros. None of the moves, as we have already seen for move (iii), alters the type of the string. Move (ii), in fact, removes three zeros of the same weight, thus reducing the weight by a multiple of 3, and does not touch the ones. Move (i) removes a multiple of 2 of ones, but alters the weight of the zeros to their left. However, if $p$ is the weight of these zeros after the move, the weight before was $4 p$, i.e., it has decreased by $3 p$, a multiple of 3.

I now prove that starting from a string of type $(a, b)$ different from $(1,2)$ it is possible to win. I start by playing move (iii) as long as I can. This step must end because each application of move (iii) adds a zero, but the number of zeros cannot exceed their total weight, which remains constant. When I can no longer play move (iii), the string must consist of $2 n+a$ ones followed by $3 m+b$ zeros. At this point I play move (i) $n$ times on the ones and move (ii) $m$ times on the zeros, obtaining a string of $a$ ones followed by $b$ zeros. Since the type $(a, b)$ is different from $(1,2)$ the sum $a+b$ must be less than three, so I have won.

I call ugly the strings consisting of $2 n+1$ consecutive ones followed by $3 m+2$ consecutive zeros: it is clear that an ugly string cannot be reduced to anything but an ugly string, and 100 is the shortest possible ugly string. Therefore, starting from an ugly string it is not possible to win. I will show in the following a strategy to win starting from strings of type $(1,2)$ that are not ugly. It follows that the only strings from which it is not possible to win are the ugly ones.

First, if the string - which from now on I assume to be of type $(1,2)$, but not ugly - ends with three or more zeros, I apply move (ii) to these until they are reduced to less than three. The string thus obtained falls into one of these forms:

A - $X 1$ with $X$ of type $(0,1)$

B - $X 10$ with $X$ of type $(0,2)$

C - $X 100$ with $X$ of type $(0,0)$.

I examine them separately.

In case A, I play the solitaire on $X$ (where I know how to win). I then reduce $X$ to 0. In this way I have reduced the initial string to 01, and I have won.

Similarly, in case B, I reduce $X$ to 00, so I have brought the string to 0010. Now I win with the moves $0010 \rightarrow 01000 \rightarrow 01$ (for clarity, I write in bold the digits on which I play a move).

Case C is slightly more complicated. I observe that $X$ is not composed of only ones, otherwise the initial string would have been ugly. So in $X$ I have at least one zero. Either this zero is the last digit of $X$, or, by repeated move (iii), I can modify $X$ to obtain a string with a zero at the end. At this point I have reduced $X 100$ to the form $Y 0100$. The type of $Y$ must be $(0,2)$. As before, I play the solitaire on $Y$ reducing it to 00. I have thus reduced the initial string to 000100. Now I win by doing $000100 \rightarrow 0010000 \rightarrow 01000000 \rightarrow 01000 \rightarrow 01$.

Observing now that 1111100000 is the only ugly string of ten digits, I have the assertion.

Second Solution: I claim that the only string of ten digits from which it is not possible to win the solitaire is 1111100000 (five ones followed by five zeros).

Step 1 I intend to prove that every string can be reduced to one of the following: $\perp, 0,1,00,10,100$ (I indicate with $\perp$ the empty string).

Given a string $s$, I consider the shortest string $s^{\prime}$ that can be obtained from it. Clearly, $s^{\prime}$ does not contain pairs of adjacent ones, so, if a one appears in it, it is at the beginning, at the end, or in a substring 010. The third case, however, is absurd, because $s^{\prime}$ could be shortened by the moves $\mathbf{0 1 0} \rightarrow \mathbf{1 0 0 0} \rightarrow 1$ (I write in bold the digits on which I play a move). Therefore, $s^{\prime}$ contains at most two ones, and an uninterrupted sequence of zeros. This, on the other hand, cannot contain more than two zeros. Therefore, the string $s^{\prime}$ is one of the strings listed above, or:

$$
\begin{aligned}
\mathbf{1 1} & \rightarrow \perp \\
101 & \rightarrow \mathbf{1 1 0 0} \rightarrow 00 \\
1001 & \rightarrow 10100 \rightarrow \mathbf{1 1 0 0 0 0} \rightarrow \mathbf{0 0 0 0} \rightarrow 0 \\
\mathbf{0 1} & \rightarrow 100 \\
0 \mathbf{0 1} & \rightarrow \mathbf{0 1 0 0} \rightarrow \mathbf{\rightarrow 1 0 0 0 0} \rightarrow 10
\end{aligned}
$$

Step 2 I prove that starting from a string $s$ that starts with a zero it is possible to win.

The string $s$ is of the form $0 X$. Using step 1, I reduce $X$ to one of the listed strings. At this point I have obtained one of the following strings: $0,00,01, \mathbf{0 0 0} \rightarrow \perp, 010 \rightarrow 1$ (as above), $\mathbf{0 1 0 0} \rightarrow 10000 \rightarrow 10$.

Step 3 Starting from a string that starts with 1, it is possible to win provided that this is not 1111100000.

I consider the case where the string consists of $2 n+a$ ones followed by $3 m+b$ zeros, with $a=0,1$ and $b=0,1,2$. Then move (iii) cannot be played, and moves (i) and (ii) have the effect of reducing $n$ and $m$ by one, respectively. I deduce that the shortest string that can be obtained is made up of $a$ ones followed by $b$ zeros. The only case in which this does not have a length greater than two is with $a=1$ and $b=2$, which, for strings of length 10, is possible only in the case 1111100000.

The remaining case is where the string starts with $n$ ones, followed by $m$ zeros, followed in turn by a one. If $n$ is even, using move (i) I reduce to the case of step 2. However, if $n$ is odd, I can use move (iii) to move the one to the right of the zeros to the left, so as to reduce to the case where the ones are even.

I do this: I consider the substring made up of $m$ zeros followed by the one. Applying move (iii) to the substring 01 that is at the bottom of this, I get a new string that starts with $m-1$ zeros followed by a one (and then two zeros). Repeating the procedure another $m-1$ times, I will have a string that starts with 10, which is what I need.