We have 1000 balls in 40 different colors, with exactly 25 balls of each color. Determine the smallest value of with the following property: if you randomly arrange the 1000 balls in a circle, there will always be consecutive balls where at least 20 different colors appear.
Solution
Consider the circle of balls where 25 balls of one color are always next to each other. To have 20 different colors, you need to take at least 18 of these groups plus one ball on one side and one ball on the other side. In total, you need at least balls next to each other. Therefore, . Now we prove that in any circle of balls, you need at most 452 balls next to each other to get 20 different colors. For this, consider any random circle of balls and all possible series of balls next to each other that together have exactly 20 colors. (There is at least one such series: take a random ball and add the balls next to it one by one until you have exactly 20 colors.) Take a series with the minimum number of balls. Say the first ball in this series is white. If there is another white ball in the series, we could have omitted the first ball to get a series with the same number of colors but fewer balls. This contradicts the minimality of the series. Therefore, there is no other white ball. In particular, the last ball in the series is not white; say it is black. We see in the same way that no other ball in the series is black. So there is one white ball, one black ball, and balls in 18 other colors, with at most 25 of each color. Together, this is at most balls. Therefore, you can always find a series of 452 balls next to each other that contains at least 20 different colors. We conclude that the required minimum is 452.