6. Alberto and Barbara are sitting next to each other in front of a table on which they have arranged in a row, from left to right, 15 chocolates. Some of the chocolates are milk, and the others are dark. Taking turns, starting with Alberto, they play the following game: during their turn, each of them must eat a strictly positive number of consecutive chocolates, always starting from the leftmost of those remaining and ensuring that the number of chocolates of the same type as the first one is odd (for example, if at a certain turn the sequence of remaining chocolates is LLFLF, where L stands for milk and F for dark, the player whose turn it is can eat the first chocolate from the left, the first 4 from the left, or all 5 chocolates).

The player who eats the last chocolate wins.

Among the $2^{15}$ possible initial sequences of the flavors of the chocolates, how many are those for which Barbara has a winning strategy?
SOLUTION: Suppose, more generally, that a player is to make a move with a row of $n$ chocolates numbered from 1 to $n$; we will denote making the move $k$, for the player's turn, as the act of eating the chocolates $\{1, \ldots, k\}$. We say that the move $k$ is legal if $1 \leq k \leq n$ and if among the chocolates $\{1, \ldots, k\}$ there is an odd number of flavor 1. We will say that a sequence of $n$ flavors is winning if the player whose turn it is, when faced with chocolates with the flavors in that sequence, has a winning strategy; the sequence will be called losing otherwise. The problem asks to determine the number of losing sequences of length 15.

We start with two simple observations:

Observation 1. If a sequence contains an odd number of occurrences of flavor 1, then it is winning (the move $L$, where $L$ is the length of the sequence, is legal and winning for the player whose turn it is).

Observation 2. Given a sequence of length $2 n+1$ with an even number of occurrences of flavor 1. If this is winning, then any winning strategy for the player whose turn it is must start with a move of the form $2 k$, where $0<k \leq n$ is such that the flavor $2 k+1$ is different from flavor 1. Indeed, if the player whose turn it is made a (legal) move of the form $2 h+1$, they would leave an odd number of chocolates of each flavor, and thus the next player would win by eating all the remaining chocolates. On the other hand, since the number of chocolates of flavor 1 left by the player whose turn it is is odd in any case, it is necessary for the sequence left to the next player to be losing that the flavor $2 k+1$ be different from flavor 1.

It will be convenient to consider for each sequence of flavors of length $n$ a corresponding sequence of zeros and ones $x_{1} x_{2} \ldots x_{n}$, constructed as follows: $x_{i}=0$ if the number of chocolates in $\{1, \ldots, i\}$ of the same flavor as 1 is even, $x_{i}=1$ otherwise. Note that $x_{1}=1$ and that to each sequence $x_{1} x_{2} \ldots x_{n} \in\{1\} \times\{0,1\}^{n-1}$ correspond exactly two sequences of flavors, both winning or both losing (thus we will speak of sequences of zeros and ones as winning or losing).

Sequences that end in 1 are all winning. Suppose a sequence of odd length ends in 0 and divide it into blocks as follows:

![](https://cdn.mathpix.com/cropped/2024_04_17_42a0ef2c084462255860g-5.jpg?height=62&width=573&top_left_y=574&top_left_x=776)

By Observation 2, if this is winning, the player whose turn it is must make a move of the form $2 k$, where the $k$-th boxed block is of the type 11 (it must be $x_{2 k}=1$ for the move to be legal and $x_{2 k+1}=x_{2 k}$ for the flavor of $2 k+1$ to be different from that of 1). This move leaves the next player a sequence of the type

$$
\begin{array}{|l|l|l|}
\hline y_{2} y_{3} & y_{4} y_{5} & \cdots \\
y_{2 n-2 k} 0 \\
\hline
\end{array}
$$

in which, since an odd number of chocolates of each flavor have been eaten, $y_{i}=x_{i+2 k}$ for $i$ odd and $y_{i} \neq x_{i}$ for $i$ even. In other words, the sequence $y_{i}$ is obtained from the sequence $x_{i}$ by deleting the first $k$ boxed blocks and, in the subsequent blocks, swapping $00,01,10,11$ with $10,11,00,01$ respectively. Among the sequences of odd length that end in 0, we distinguish three cases:

(i) there are no 11 blocks; then the sequence is losing by Observation 2;

(ii) the last 11 block, say the $k$-th, has no 01 blocks to its right; then the sequence is winning: the move $k$ is legal and leaves the opponent a sequence of type (i) (which also ends in 0 and has odd length);

(iii) the last 11 block has a 01 block to its right; then the sequence is losing, because any choice of a 11 block leaves the opponent a sequence of type (ii), which is winning.

In summary, we need to count the sequences of type (i) and (iii) of length 15. It involves choosing the content of 7 blocks from the possibilities $\{\boxed{00}, 01,10,11\}$ while respecting the given conditions. There are always two possibilities for the last block, which is of type $10$ or $00$. The sequences in which neither 11 nor 01 appear, which are losing, are $2^{7}$. Among the sequences in which at least one 11 or 01 block appears and such that the last block is 10 or 00, those of type (i) or (iii) are exactly half: this is because a sequence is of type (i) or (iii) if and only if the sequence obtained by swapping 11 blocks with 01 and vice versa is not. We must therefore add $\frac{2 \times 4^{6}-2^{7}}{2}=2^{12}-2^{6}$ losing sequences.

Remembering that each losing sequence of zeros and ones corresponds to two original losing sequences, we have a total of $2\left(2^{7}+2^{12}-2^{6}\right)=2\left(2^{6}+2^{6}+2^{12}-2^{6}\right)=2^{7}+2^{13}$ losing sequences.

## SECOND SOLUTION:

Since the problem concerns a sequence of 15 chocolates, and 15 is an odd number, we can assume that the sequence consists of $n=2 k+1$ chocolates.

We observe that if the type of chocolate that appears first on the left appears an odd number of times, then Alberto wins by eating all the chocolates on the first move.

Suppose, then, that the chocolate on the far left appears an even number of times, which corresponds to $2^{2 k}$ cases, and suppose that among them $a_{k}$ is the number of times Alberto has a winning strategy and $b_{k}$ is the number of times Barbara has a winning strategy.

With an immediate check, we find $b_{0}=0$ and $b_{1}=4$. Suppose now $k \geq 2$ and thus $n=2 k+1 \geq 5$. First, consider the case where the sequence of chocolates ends with two chocolates of the same type, i.e., LL or FF, thus in a total number of cases equal to $2^{n-2}$. In this case, it is clear that the one who manages to make the last move to eat the first $n-2$ chocolates can also eat the other two, and thus there are $2 b_{k-1}$ cases in which Barbara wins.

Now suppose the last two chocolates are of different types, for example, LF, and consider the type of the first and third-to-last chocolates. In the case where these types are different, LF or FL, Alberto wins if he makes the (legal) move of eating all the chocolates except the last 3. If, instead, the first and third-to-last chocolates are of the same type, for example, LL, Alberto, who cannot eat all the chocolates, must leave Barbara a non-empty sequence of chocolates. If the remaining sequence starts with L, Barbara can eat all the remaining, and thus wins. If the remaining sequence starts with F, then either the number of F remaining is odd, and thus Barbara wins by eating all the remaining chocolates, or the number of F remaining is even, and then Barbara wins by leaving Alberto the last 3 chocolates. The case where the first and third-to-last chocolates are of type FF is analogous.

In conclusion, Barbara wins in all cases where the first and third-to-last chocolates are of the same type and the last two are of different types. Since we are only considering the case where the number of chocolates of the same type as the first is even, this gives rise to $2^{n-3}=2^{2 k-2}$ possibilities.

This provides the recursive formula

$$
b_{k}=2 b_{k-1}+2^{2 k-2}
$$

and thus allows calculating in a few steps $b_{7}=8320$, which is the number sought.

Note: With classical techniques, the recursive formula allows deriving a closed formula, which in this case is $b_{k}=2^{k}+\frac{1}{2} 4^{k}$.