A problem about the existence of increasing coloring groups

Question

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.

Answer 1

This follows directly from the following

Theorem. Assume that $n\geqslant k>0$ are integers; $0\leqslant a_1\leqslant a_2\leqslant \ldots \leqslant a_n$ are non-negative integers; we have $a_i$ balls with label $i$, and want to color them in $k$ colors nicely, that is, different colors have different number of distinct labels, and each color being used for at least one ball. This is possible if and only if the following condition N: $$a_1+\ldots+a_{n-j}\geqslant (k-j)(k-j+1)/2\tag{$\star$}$$ for all $j=0,1,\ldots,k-1$, holds.

Proof.

1. If a nice coloring exists, Condition N holds.

Indeed, let the color $i$ have $b_i$ distinct labels so that $0<b_1<b_2<\ldots<b_k$. Look at the following $k-j$ colors: $j+1,\ldots,k$. They have in total not less than $(j+1)+\ldots+k$ labels. This includes at most $j(k-j)$ labels belonging to the set of labels $\{n-j+1,\ldots,n\}$. Therefore at least $((j+1)+\ldots+k)-j(k-j)=1+\ldots+(k-j)=(k-j)(k-j+1)/2$ labels must be realized by at most $a_1+\ldots+a_{n-j}$ balls with labels at most $n-j$.

2. If condition N holds, a nice coloring exists. Note that Condition N may be reformulated in the terms which do not appeal to the ordering of $a_i$'s: for each $j=1,2,\ldots, k$ for any $n-j$ labels there exist at least $(k-j)(k-j+1)/2$ balls of these labels.

The claim clearly holds for $k=1$. So, using induction we may assume that $k>1$ and it holds for $k-1$. $(\star)$ for $j=k-1$ yields $a_1+\ldots+a_{n-(k-1)}\geqslant 1$, equivalently, $a_{n-k+1}>0$. Call labels $n-k+1,\ldots,n$ joyful. We may take one ball with each joyful label and color them all in color $k$. If we verify that the remaining balls satisfy Condition N for $k-1$ colors, we may color some of them in colors $1,2,\ldots,k-1$ so that there exist exactly $i$ distinct labels for the $i$-th color for $i=1,2,\ldots,k-1$. Coloring all other balls in color $k$ we get a nice coloring.

For verifying Condition N for the new collection of balls and $k-1$ colors, we should prove that for each $j=1,2,\ldots, k-2$ for any $n-j$ chosen labels there exist at least $(k-1-j)(k-j)/2$ balls of these chosen labels. Let there be $n-k-i$ not joyful chosen labels and $k+i-j$ joyful chosen labels, here $i$ is between $0$ and $\min(j,n-k)$. There exist at least $a_1+\ldots+a_{n-k-i}$ balls of not joyful chosen labels and at least $(a_{n-k+1}-1)+\ldots+(a_{n-k+(k+i-j)}-1)=a_{n-k+1}+\ldots+a_{n+i-j}-(k+i-j)$ balls of joyful chosen labels. Between $k+2i-j$ numbers $a_{n-k-i+1},\ldots,a_{n+i-j}$ the $k+i-j$ numbers $a_{n-k+1},\ldots,a_{n+i-j}$ are the largest. Thus $$ a_{n-k+1}+\ldots+a_{n+i-j}\geqslant \frac{k+i-j}{k+2i-j}(a_{n-k-i+1}+\ldots+a_{n+i-j}). $$ Also, obviously, $$ a_{1}+\ldots+a_{n-k-i}\geqslant \frac{k+i-j}{k+2i-j}(a_{1}+\ldots+a_{n-k-i}). $$ Summing up and using $(\star)$ for $j-i$ at place of $j$ we get $$ (a_{1}+\ldots+a_{n-k-i})+(a_{n-k+1}+\ldots+a_{n+i-j}) \geqslant \frac{k+i-j}{k+2i-j}(a_1+\ldots+a_{n+i-j})\\ \geqslant \frac{k+i-j}{k+2i-j}\cdot \frac{(k-j+i)(k-j+i+1)}2=:A $$ It suffices to prove that $A\geqslant (k+i-j)+(k-j)(k-j-1)/2$. Well, $$2A-2(k+i-j)-(k-j)(k-j-1)=\frac{i(k+i-j-1)(k+2i-j-1)}{k+2i-j}.$$ Since $j\leqslant k-1$, this is non-negative.