Maths Olympiad Prep

Library / /35 of 36

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Italy

Problem:

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 chocolate, the others dark chocolate. Taking turns, starting with Alberto, they play the following game: during one's turn, each of the two must eat a strictly positive number of consecutive chocolates, always starting from the leftmost one among those remaining, and doing so in such a way that the number of chocolates eaten 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 chocolate and FF for dark chocolate, the player whose turn it is may eat the first chocolate from the left, the first 4 from the left, or all 5 chocolates).

Whoever eats the last chocolate wins.

Among the 2152^{15} possible initial sequences of chocolate flavors, how many are there for which Barbara has a winning strategy?

Solution

Solution:

Suppose, more generally, that a player has to make a move with a row of nn chocolates numbered from 1 to nn; we will denote by making move kk, for the player whose turn it is, the act of eating the chocolates {1,,k}\{1, \ldots, k\}. We will say that move kk is legal if 1kn1 \leq k \leq n and if among the chocolates {1,,k}\{1, \ldots, k\} there is an odd number of the flavor of 1. We will say that a sequence of nn flavors is winning if the player whose turn it is, faced with chocolates having the flavors in such a sequence, possesses a winning strategy; the sequence will be called losing otherwise. The problem asks to determine the number of losing sequences of length 15.

Let us begin with two simple observations:

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

Observation 2. Consider a sequence of length 2n+12n+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 begin with a move of the form 2k2k, where 0<kn0 < k \leq n is such that flavor 2k+12k+1 is different from flavor 1. Indeed, if the player whose turn it is were to make a (legal) move of the form 2h+12h+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 over by the player whose turn it is is in any case odd, it is necessary, in order for the sequence left to the next player to be losing, that flavor 2k+12k+1 be different from flavor 1.

We will find it convenient to consider, for each sequence of flavors of length nn, a corresponding sequence of zeros and ones x1x2xnx_{1} x_{2} \ldots x_{n}, constructed as follows: xi=0x_{i}=0 if the number of chocolates in {1,,i}\{1, \ldots, i\} of the same flavor as 1 is even, xi=1x_{i}=1 otherwise. Note that x1=1x_{1}=1 and that to each sequence x1x2xn{1}×{0,1}n1x_{1} x_{2} \ldots x_{n} \in \{1\} \times \{0,1\}^{n-1} there correspond exactly two sequences of flavors, both winning or both losing (thus we will speak of sequences of zeros and ones as being in turn winning or losing).

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

Figure 1

By Observation 2, if this is winning the player whose turn it is must make a move of type 2k2k, where the kk-th boxed block is of type 11 (we must have x2k=1x_{2k}=1 in order for the move to be legal and x2k+1=x2kx_{2k+1}=x_{2k} in order for the flavor of 2k+12k+1 to be different from that of 1). Such a move leaves the next player a sequence of the type
y2y3y4y5y2n2k0 \begin{array}{|l|l|l|} \hline y_{2} y_{3} & y_{4} y_{5} & \cdots \\ y_{2n-2k} 0 \\\hline \end{array}
in which, since an odd number of chocolates of each flavor has been eaten, yi=xi+2ky_{i}=x_{i+2k} for ii odd and yixiy_{i} \neq x_{i} for ii even. In other words, the sequence yiy_{i} is obtained from the sequence xix_{i} by deleting the first kk boxed blocks and, in the following blocks, swapping 00,01,10,1100,01,10,11 with 10,11,00,0110,11,00,01 respectively. Among sequences of odd length ending 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 kk-th, has no 01 blocks to its right; then the sequence is winning: move kk 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 an 11 block leaves the opponent a sequence of type (ii), which is winning.

Summing up, we must count sequences of type (i) and (iii) of length 15. This amounts to choosing the content of 7 blocks among the possibilities {00,01,10,11}\{\boxed{00}, 01,10,11\} respecting the given conditions. There are always two possibilities for the last block, which is of type 1010 or 0000. The sequences in which neither 11 nor 01 appears, which are losing, are 272^{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 changing the 11 blocks to 01 and vice versa is not. We must therefore add 2×46272=21226\frac{2 \times 4^{6}-2^{7}}{2}=2^{12}-2^{6} losing sequences.

Recalling that to each losing sequence of zeros and ones there correspond two original losing sequences, we thus have a total of 2(27+21226)=2(26+26+21226)=27+2132\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.

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

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

Suppose then that the leftmost chocolate appears an even number of times, which corresponds to 22k2^{2k} cases, and suppose that among these aka_{k} is the number of times Alberto has a winning strategy and bkb_{k} is the number of times Barbara has a winning strategy.

By immediate verification we find b0=0b_{0}=0 and b1=4b_{1}=4. Suppose now k2k \geq 2 and hence n=2k+15n=2k+1 \geq 5. Let us first consider the case in which the sequence of chocolates ends with two chocolates of the same type, i.e. LL or FFFF, hence overall in a number of cases equal to 2n22^{n-2}. In this case it is clear that whoever manages to make the last move to eat the first n2n-2 chocolates can also eat the other two as well, and hence there are 2bk12b_{k-1} cases in which Barbara wins.

Suppose now that the last two chocolates are of different type, for example LF, and consider the type of the first and of the third-to-last of the 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 the third-to-last of the chocolates are of the same type, for example LL, Alberto, who cannot eat all the chocolates, must leave Barbara a nonempty sequence of chocolates. If the remaining sequence begins with L, Barbara can eat all the remaining ones, and hence wins. If the remaining sequence begins with FF, then either the number of F's remaining is odd, and hence Barbara wins by eating all the remaining chocolates, or the number of FF's remaining is even, and then Barbara wins by leaving Alberto the last 3 chocolates. The case where the first and third-to-last chocolate are of type FF is analogous.

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

This provides the recursive formula
bk=2bk1+22k2 b_{k}=2b_{k-1}+2^{2k-2}
and hence allows us to compute in a few steps b7=8320b_{7}=8320, which is the number sought.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.