Problem

Source: ITAMO 2019 #6

Tags: combinatorics, ITAMO 2019



Alberto and Barbara are sitting one next to each other in front of a table onto which they arranged in a line $15$ chocolates. Some of them are milk chocolates, while the others are dark chocolates. Starting from Alberto, they play the following game: during their turn, each player eats a positive number of consecutive chocolates, starting from the leftmost of the remaining ones, so that the number of chocolates eaten that are of the same type as the first one is odd (for example, if after some turns the sequence of the remaining chocolates is $\text{MMDMD},$ where $\text{M}$ stands for $\emph{milk}$ and $\text{D}$ for $\emph{dark},$ the player could either eat the first chocolate, the first $4$ chocolates or all $5$ of them). The player eating the last chocolate wins. Among all $2^{15}$ possible initial sequences of chocolates, how many of them allow Barbara to have a winning strategy?