Got stuck on this one for months.

Given a sequence of non decreasing positive integers $a_1, .., a_n$, let there be $a_i$ balls labeled the number i, for each $1 \leq i \leq n$. Suppose there is a k coloring of the balls where different color has different number of distinct labels. Let’s call this a special k coloring on $a_1, .., a_n$.

Now suppose we add $a_{n+1}$ more balls labeled $n+1$, where $\sum_{i=1}^{n+1} a_i \geq (k+1)(k+2)/2$ and $a_{n+1} \geq a_n$. Show that there is a special $k+1$ coloring on $a_1, \ldots, a_{n+1}$.

Note that special k coloring implies there are at least 1 distinct labels of color 1, 2 distinct labels of color 2, $\ldots$, k distinct labels of color k, for some ordering of the k colors.

PS: my previous version stated that each color group can contain at most one ball of any given label i. But that makes the claim false as pointed out by Fedor.

Got stuck on this one for months.

Given a sequence of non decreasing positive integers $a_1, .., a_n$, let there be $a_i$ balls labeled the number i, for each $1 \leq i \leq n$. Suppose there is a k coloring of the balls where different color has different number of distinct labels. Let’s call this a special k coloring on $a_1, .., a_n$.

Now suppose we add $a_{n+1}$ more balls labeled $n+1$, where $\sum_{i=1}^{n+1} a_i \geq (k+1)(k+2)/2$ and $a_{n+1} \geq a_n$. Show that there is a special $k+1$ coloring on $a_1, \ldots, a_{n+1}$.

Note that special k coloring implies there are at least 1 distinct labels of color 1, 2 distinct labels of color 2, $\ldots$, k distinct labels of color k, for some ordering of the k colors.

PS: my previous version required that each color group contain at most one ball of any given label i. But that makes the claim false as pointed out by Fedor.

Got stuck on this one for months.

Given a sequence of non decreasing positive integers $a_1, .., a_n$, let there be $a_i$ balls labeled the number i, for each $1 \leq i \leq n$. Suppose there is a k coloring of the balls where each number i appears at most once in each color and different color has different number of balls. Let’s call this a special k coloring on $a_1, .., a_n$.

Now suppose we add $a_{n+1}$ more balls labeled $n+1$, where $\sum_{i=1}^{n+1} a_i \geq (k+1)(k+2)/2$ and $a_{n+1} \geq a_n$. Show that there is a special $k+1$ coloring on $a_1, \ldots, a_{n+1}$.

Note that special k coloring implies there are at least 1 ball of color 1, 2 balls of color $2, \ldots, k$ balls of color k, with no repeated number within each color.

Got stuck on this one for months.

Given a sequence of non decreasing positive integers $a_1, .., a_n$, let there be $a_i$ balls labeled the number i, for each $1 \leq i \leq n$. Suppose there is a k coloring of the balls where different color has different number of distinct labels. Let’s call this a special k coloring on $a_1, .., a_n$.

Now suppose we add $a_{n+1}$ more balls labeled $n+1$, where $\sum_{i=1}^{n+1} a_i \geq (k+1)(k+2)/2$ and $a_{n+1} \geq a_n$. Show that there is a special $k+1$ coloring on $a_1, \ldots, a_{n+1}$.

Note that special k coloring implies there are at least 1 distinct labels of color 1, 2 distinct labels of color 2, $\ldots$, k distinct labels of color k, for some ordering of the k colors.

PS: my previous version stated that each color group can contain at most one ball of any given label i. But that makes the claim false as pointed out by Fedor.