
5. Kira has 3 blocks with the letter A, 3 blocks with the letter B, and 3 blocks with the letter C. She puts these 9 blocks in a sequence. She wants to have as many distinct distances between blocks with the same letter as possible. For example, in the sequence ABCAABCBC the blocks with the letter A have distances 1, 3, and 4 between one another, the blocks with the letter B have distances 2, 4, and 6 between one another, and the blocks with the letter $\mathrm{C}$ have distances 2, 4 , and 6 between one another. Altogether, we got distances of $1,2,3,4$, and 6 ; these are 5 distinct distances.

What is the maximum number of distinct distances that can occur?



5. We will show that the maximum number of distinct distances is 7 . First we prove that the number of distinct distances cannot be more than 7 , then we will show that there is a sequence of blocks with 7 distances.

The possible distances between two blocks in the sequence are the numbers 1 to 8 . Therefore, there can certainly be no more than 8 distinct distances. We will show that there is always at least one distance that does not occur.

If in a sequence the distances 8 and 7 do not both occur, we are done. Therefore, suppose we have a sequence in which these two distances do both occur. The distance 8 can only occur between the very first and the very last block, so these should have the same letter on them, say A. The distance 7 can only occur between the first and the eighth (second last) block, or between the second and the last block. Because both outer blocks have an A, the second or eighth block must also have an A. Then the sequence of blocks is AAxxxxxxA (or the other way around: AxxxxxxAA), where on the place of $x$ are blocks with a $B$ or $C$. Now we see that the distance 6 cannot occur anymore: the distances between the blocks with $\mathrm{A}$ are 1, 7, and 8, and the distances between the blocks with B and the blocks with $\mathrm{C}$ are at most 5 . Also in this case, there is at least one distance that does not occur.

We conclude that there is always one of the possible distances $1,2,3,4,5,6,7,8$ that does not occur. Hence, the number of distinct distances cannot be more than 7 .

An example of a sequence of blocks where 7 distinct distances occur, is ABBCACCBA, with distances $4,4,8 ; 1,5,6 ; 1,2,3$ (only the distance 7 is missing). So the maximal number of distinct distances is equal to 7 .

