Maths Olympiad Prep

Library / /20 of 24

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Netherlands

Kira has 33 blocks with the letter AA, 33 blocks with the letter BB, and 33 blocks with the letter CC. She puts these 99 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 ABCAABCBCABCAABCBC the blocks with the letter AA have distances 11, 33, and 44 between one another, the blocks with the letter BB have distances 22, 44, and 66 between one another, and the blocks with the letter CC have distances 22, 44, and 66 between one another. Altogether, we got distances of 11, 22, 33, 44, and 66; these are 55 distinct distances.
What is the maximum number of distinct distances that can occur?

Solution

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

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

If in a sequence the distances 88 and 77 do not both occur, we are done. Therefore, suppose we have a sequence in which these two distances do both occur. The distance 88 can only occur between the very first and the very last block, so these should have the same letter on them, say AA. The distance 77 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 AA, the second or eighth block must also have an AA. Then the sequence of blocks is AAxxxxxxAAAxxxxxxA (or the other way around: AxxxxxxAAAxxxxxxAA), where on the place of xx are blocks with a BB or CC. Now we see that the distance 66 cannot occur anymore: the distances between the blocks with AA are 11, 77, and 88, and the distances between the blocks with BB and the blocks with CC are at most 55. 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 11, 22, 33, 44, 55, 66, 77, 88 that does not occur. Hence, the number of distinct distances cannot be more than 77.

An example of a sequence of blocks where 77 distinct distances occur, is ABBACCBAABBACCBA, with distances 44, 44, 88; 11, 55, 66; 11, 22, 33 (only the distance 77 is missing). So the maximal number of distinct distances is equal to 77. ☐

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 and solution reproduced as published; topic and difficulty added by this site.