Maths Olympiad Prep

Library / /229 of 520

Combinatorics Difficulty 6.4 National olympiad Find the answer

We have 1000 balls in 40 different colors, with exactly 25 balls of each color. Determine the smallest value of nn with the following property: if you randomly arrange the 1000 balls in a circle, there will always be nn consecutive balls where at least 20 different colors appear.

A number or a short expression. Spacing and $ signs are ignored.

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 1825+2=45218 \cdot 25 + 2 = 452 balls next to each other. Therefore, n452n \geq 452. 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 1825+2=45218 \cdot 25 + 2 = 452 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 nn is 452.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.