Problem

Source: VMO 2021 P6 Vietnam National Olympiad

Tags: combinatorics, Coloring



A student divides all $30$ marbles into $5$ boxes numbered $1, 2, 3, 4, 5$ (after being divided, there may be a box with no marbles). a) How many ways are there to divide marbles into boxes (are two different ways if there is a box with a different number of marbles)? b) After dividing, the student paints those $30$ marbles by a number of colors (each with the same color, one color can be painted for many marbles), so that there are no $2$ marbles in the same box. have the same color and from any $2$ boxes it is impossible to choose $8$ marbles painted in $4$ colors. Prove that for every division, the student must use no less than $10$ colors to paint the marbles. c) Show a division so that with exactly $10$ colors the student can paint the marbles that satisfy the conditions in question b).