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 $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?
Problem
Source: Dutch NMO 2022 p5
Tags: combinatorics
straight
18.11.2022 02:10
The answer is $6$, with construction for example $ABBCACCBA$. For $7$ distances to occur, we need either distance $8$ with distance $7$,distance $8$ with distance $6$ or distance $6$ with distance $7$ (it is easy to check that all three can't occur at the same time). Then it's just way too much casework.
Harote
09.09.2023 04:16
There is 9 distance but there cannot be 2 letters in a block so the minimum is 1 and all the letters are next to each other so the greatest distance is from the ends which is 8 with the 9 letter blocks, so the maximum for now is 8. Now I am going to demonstrate by cases that among those 8 distances, one will not be able to be with the rest. -First let's go to the case from greatest to least For the distance 8, a block is needed from end to end, let's say $A_1$ and $A_3$, for 7 to exist with 8, $A_2$ needs to be next to $A_1$ or $A_3$, but then in no way can a 6 be created because there are 6 squares left. and from end to end there are 5 and we cannot use $A_4$ either -Now let's go to the case without 7 If we skip the 7 then with the ends of the 7 remaining block spaces we can put $B_1$ and $B_3$ to have the distance 6 but for 5 we would have to put $B_2$ next to $B_1$ or $B_3$ but then we wouldn't have a distance 4 or that would be it but we still have $A_2$ since we skipped distance 7, and distance 4 from the ends is the center. With this we finish if we put the C in the remaining blocks that gives distance 3,2 and 1 We have 7 different distances now let's give an example: ABBCACCBA ABCCACBBA so our answer is 7