TUYMAADA 2024 J8

A toy factory produces several kinds of clay toys. The toys are painted in $k$ colours. Diversity of a colour is the number of different toys of that colour. (Thus, if there are $5$ blue cats, $7$ blue mice and nothing else is blue, the diversity of colour blue is $2$ .) The painting protocol requires that each colour is used and the diversities of each two colours are different. The toys in the store could be painted according to the protocol. However, a batch of clay Cheburashkas arrived at the store before painting (there were no Cheburashkas before). The number of Cheburashkas is not less that the number of the toys of any other kind. The total number of all toys, including Cheburashkas, is at least $\frac{(k+1)(k+2)}{2}$ . Prove that now the toys can be painted in $k + 1$ colours according to the protocol. Proposed by F. Petrov