There are $2014$ balls with $106$ different colors, $19$ of each color. Determine the least possible value of $n$ so that no matter how these balls are arranged around a circle, one can choose $n$ consecutive balls so that amongst them, there are $53$ balls with different colors.
Problem
Source: Turkey Junior MO 2014 Problem 3
Tags: pigeonhole principle, combinatorics, Turkey
17.11.2014 14:12
It looks too easy for Turkey. The answer is $51\cdot 19+2$. An example where we need that much is trivial; just let the balls be in blocks of $19$ balls where all the balls that are in the same block are the same color. Now the proof. Consider any $51\cdot 19+2$ balls. Now,suppose we don't have $53$ colors. Pick the ball that is nearest to these $51\cdot 19+2$ balls and has a color different from the color of any ball among these $51\cdot 19+2$ balls. Now, just rotate these $51\cdot 19+2$ and consider consecutive balls that start with that nearest ball. The nearest ball will be the only ball of its color among the new $51\cdot 19+2$ balls, so it is an easy pigenhole on $51\cdot 19+1$ balls that they will have balls that are of at least $52$ colors, and we are finished.
17.11.2014 15:46
The solution is $971=51*19+2$ To find an example where no amount under $971$ will work, just arrange them in a fashion so that every $19$ same colored balls are next to one another. Now to prove that a row of $971$ balls is sufficient for any arrangement. Let's assume it doesn't. This means that every row of $2014-971=1043$ contains at least $54$ groups of $19$ balls of the same colour. Since $1043-19*54=17<19$ this means that there will be exactly $54$ groups of $19$ balls of the same colour in every row of $1043$ balls and $17$ more balls. Let's chose a row of $1043$ that satisfies the given conditions. When rotating the every chosen ball by $1$ (for example if the chosen row was $1,2,3....1043$ then the new row will be $2,3,....1044$) we will once again need $54$ groups of $19$ balls and the pool of balls will mostly remain the same with the inclusion and exclusion of $1$ ball. Since the max number of members of the same colour is $17$(not counting those which are full meaning all $19$ are included in the given row) the inclusion of one new ball can't be enough to complete its group. Hence, we have that in our new row we shall have the same sets of $19$ balls as in our previous. By repetition, we get a contradiction.