Browse · MathNet
PrintFinal Round
Netherlands counting and probability
Problem
Kira has blocks with the letter , blocks with the letter , and blocks with the letter . She puts these 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 the blocks with the letter have distances , , and between one another, the blocks with the letter have distances , , and between one another, and the blocks with the letter have distances , , and between one another. Altogether, we got distances of , , , , and ; these are 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 . First we prove that the number of distinct distances cannot be more than , then we will show that there is a sequence of blocks with distances.
The possible distances between two blocks in the sequence are the numbers to . Therefore, there can certainly be no more than distinct distances. We will show that there is always at least one distance that does not occur.
If in a sequence the distances and do not both occur, we are done. Therefore, suppose we have a sequence in which these two distances do both occur. The distance can only occur between the very first and the very last block, so these should have the same letter on them, say . The distance 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 , the second or eighth block must also have an . Then the sequence of blocks is (or the other way around: ), where on the place of are blocks with a or . Now we see that the distance cannot occur anymore: the distances between the blocks with are , , and , and the distances between the blocks with and the blocks with are at most . 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 , , , , , , , that does not occur. Hence, the number of distinct distances cannot be more than .
An example of a sequence of blocks where distinct distances occur, is , with distances , , ; , , ; , , (only the distance is missing). So the maximal number of distinct distances is equal to . ☐
The possible distances between two blocks in the sequence are the numbers to . Therefore, there can certainly be no more than distinct distances. We will show that there is always at least one distance that does not occur.
If in a sequence the distances and do not both occur, we are done. Therefore, suppose we have a sequence in which these two distances do both occur. The distance can only occur between the very first and the very last block, so these should have the same letter on them, say . The distance 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 , the second or eighth block must also have an . Then the sequence of blocks is (or the other way around: ), where on the place of are blocks with a or . Now we see that the distance cannot occur anymore: the distances between the blocks with are , , and , and the distances between the blocks with and the blocks with are at most . 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 , , , , , , , that does not occur. Hence, the number of distinct distances cannot be more than .
An example of a sequence of blocks where distinct distances occur, is , with distances , , ; , , ; , , (only the distance is missing). So the maximal number of distinct distances is equal to . ☐
Final answer
7
Techniques
Coloring schemes, extremal arguments