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?
Problem
Source: ITAMO 2019 #6
Tags: combinatorics, ITAMO 2019
Pathological
04.05.2019 07:20
Let's call a configuration of $M$'s and $D$'s $\mathbf{winnable}$ if the first player will win if they play the described game starting from this configuration, and $\mathbf{vengeful}$ otherwise. Firstly, it's immediate that if there are an odd number of chocolates of the same type as the first one, then the configuration is winnable (just eat them all). Call these configurations $\mathbf{trivial}.$ Otherwise, for a nontrivial configuration, the player whose turn it is will want to eat some chocolates so that the leftmost remaining chocolate is of a different type as the first chocolate. This is clear, since otherwise the other player can win on the next move. Furthermore, whenever there are an even number of chocolates after the move of one of the players, there must be an odd number of chocolates of both types, and so the other player would win since the configuration is trivial. Therefore, the player whose turn it is will want to ensure that after his move, there are still an odd number of chocolates remaining. Hence, we've established that we can assume, WLOG, that both players will ensure that after their move:
1) There are an odd number of remaining chocolates, and
2) The leftmost chocolate is of a different type than it was before his/her move
Furthermore, the first player who doesn't play in this way loses.
Let's call a configuration $\mathbf{milksafe}$ if it has an odd number of chocolates, the leftmost one is milk chocolate, and it's nontrivial. Define $\mathbf{darksafe}$ similarly. Then, for an arbitrary configuration of $15$ chocolates, we'll place a $'$ before all of its milksafe suffixes and a $|$ before all of its darksafe suffixes, with the sole exception that we don't put anything before the suffix which is the entire configuration. For instance, if our configuration is $MMDMDMMDMMDMDMM$, then it will turn into:
$$MMDM|DM'MDMM|DMDMM,$$
after placing the "dividers" accordingly. Note that we didn't put a $'$ at the front. We will now describe a characterization of all winning configurations. Firstly, let's assume WLOG that the leftmost chocolate is initially milk chocolate (the other case is analogous). Then, we claim that Barbara wins if and only if the rightmost $'$ is to the right of the rightmost $|$. In particular, if there is no $'$ anywhere but there is a $|$, then Barbara loses, and if there is no $|$ anywhere but there is a $'$ than Barbara wins. To see this, firstly note that by our assumption above, Alberto must always play on divisibility signs and Barbara on apostrophes. Therefore, if there are no $|$ anywhere, then Barbara can win on the next move due to our work above. If there are $|$ and there are no apostrophes to the right of the rightmost $|$, then Barbara loses since Alberto can move to the rightmost $|$ on his first move. Afterwards, Barbara cannot move to a milksafe suffix, and so she loses. Finally, if there are $|$ and there is an apostrophe to the right of the rightmost $|$, then Barbara can win on her second move by simply moving to the rightmost apostrophe on her first move. On Albert's second move, he cannot move to a darksafe suffix and so he loses.
We have now characterized all winning configurations by describing an easy way to determine winnability by looking at darksafe and milksafe suffixes, and so we're done.
FedeX333X
04.05.2019 16:49
Sorry, I mistyped the problem yesterday; actually it's also asking for the number of winning configuration, not only for which ones.
Idio-logy
28.10.2019 03:14
Denote dark chocolates by $1$ and milk chocolates by $2$, and let the string of chocolates we study be $S$, which consists of characters $1$ and $2$. First, we need to come up with a characterization of games in which Barbara (player B) has a winning strategy. It's easy to see that without loss of generality, we can suppose that the first chocolate is $1$.
We start from the easy cases. If the total number of $1$ is odd, then player A can take all chocolates and win. If the total number of $1$ is even, suppose that $S'$ is the resulting string after he finishes choosing a block of consecutive numbers. Notice that $S'$ contains an odd number of $1$s, because player A just took away an odd number of $1$s. Thus, if $S'$ starts with a $1$ or if $S'$ starts with $2$ and contains an odd number of $2$, then B will be able to take all the chocolates and win. Thus $S'$ starts with $2$ and contains an even number of $2$s.
The game continues in this way, each player trying to not let the other win until some player is not able to do so. The above discussion motivates us to insert dividers in the string $S$. Insert an A-divider at all such places that the sequence $S'$ after the divider starts with a $2$, and contains an even number of $2$s and an odd number of $1$s. Similarly, insert a B-divider at all such places that the sequence $S'$ after the divider starts with a $1$, and contains an even number of $1$s and an odd number of $2$s. For example, for the string $$1212221221112$$the dividers are inserted as such: $$/121222/12\backslash 21/112$$where $\backslash$ are A-dividers and $/$ are B-dividers.
After the definitions, the key claim is that:
Claim. If there is an even number of $1$s at the start, then player B has a winning strategy if and only if the last divider is a B-divider or that there are no B-dividers.
Proof. We only need to prove that "the last divider is a B-divider or there are no dividers" implies "player B has a winning strategy", and that "the last divider is an A-divider" implies "player A has a winning strategy". Suppose the last divider is a B-divider. Then according to our discussion above, in order for A to win, the blocks he choose must end with an A-divider. But since the last divider is a B-divider, whatever A takes, B can directly take the characters all the way to the last divider, which is a B-divider. This block starts with a $2$, and contains an odd number of $2$s in it (even $-$ odd), so this operation is legitimate. Then there are no A-dividers for A to use, meaning that B wins. If there are no dividers, then since A goes first, he loses. On the other hand, if the last divider is an A-divider, then A can take chocolates all the way to the last A-divider. The number of $1$s in this block is odd (even $-$ odd), so this move is legitimate, and it makes player A win. $\square$
Now we compute the quantity we want. Notice that the dividers can only be inserted at odd-numbered places if we number them as below: $$1\thinspace\square\thinspace\square\thinspace 3\thinspace\square\thinspace\square\thinspace\dots 13\thinspace\square\thinspace\square\thinspace 15\thinspace\square$$where the squares stand for chocolates. Call the two squares between $(2k-1)$ and $(2k+1)$ the $k$th pair for $1\le k\le 7$, and call the last square the singleton. If there exists a divider, suppose that the last one is at the $(2i-1)$th place. The singleton has two choices; each pair after the $i$th pair also has two choices, since the first number of each pair is arbitrary, and the second is uniquely determined by the first in order for there to be no dividers after the $i$ th place. The first number in the $i$th pair must be $1$ (since it's a B-divider), and the second number in the $i$th pair is uniquely determined by the first so that there is a B-divider at the $(2i-1)$th place. This gives $2^{8-i}$ choices for numbers from the $i$th pair to the end. For the other numbers, we need to ensure that there is an even number of $1$s. Since there is a B-divider at the $(2i-1)$th place, the number of $1$s after it is even. So the number of $1$s before it must be even too. This gives $2^{2i-4}$ choices when $2\le i\le 7$ and $1$ choice when $i=1$. Summing them all over $i$, we have $$2^7+\sum_{i=2}^{7} 2^{2i-4}\cdot 2^{8-i}=2^{12}+2^6.$$If there are no dividers, then since the first number is $1$, there is an odd number of $1$s, meaning that this doesn't contribute to the total count.
Finally, remembering that the first number can be either $1$ or $2$, the total sum is $2^{13}+2^7=\boxed{8320}$.
P.S. I don't know if this answer is correct or not, so if you have spotted any mistakes please tell me.
minecraftfaq
29.05.2021 10:35
@above I have a better way to count. There are $2^7$ choices of no-dividers-situations, and among other situations, half of them ends with B-divider, that is $$\frac{2^{13}-2^7}{2}$$Thus, there are $2^7+\frac{2^{13}-2^7}{2}=2^{12}+2^6$ choices. The answer is $2*(2^{12}+2^6)=2^{13}+2^7=8320$.
DofL
29.05.2021 11:24
ngl, this sort of is like a tastier version of Nim