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).
Problem
Source: VMO 2021 P6 Vietnam National Olympiad
Tags: combinatorics, Coloring
17.02.2022 06:04
a) This is just Euler’s candy division theorem. b) Assume that A is the highest number of marbles in a box. Due to pigeonhole principle we can see that A is no less than 6. Assume that there exist a way to divide 30 marbles in 5 boxes and paint them so that the student use less than 10 colors and satisfy all the data (so this mean 5<A<10). Since from 2 boxes it is impossible to choose 8 marbles painted in 4 colors, in a pair of box there are at most 3 same colors. As a result, if A are 7,8,9, than there is another box contains 6 marbles due to the pigeonhole principle and these two boxes will you no less than 10 colors (because the box with A marbles will have no less than 7 different colors, and the other box will have another 3 different colors). So the only situation can satisfy the assumption is each box has 6 marbles. If the box 1 has colors 1 2 3 4 5 6, so box 2 has to contain 3 colors from box 1. WLOG, assume that they are 1 2 3, then box 2 contains 1 2 3 7 8 9. The only way to paint for the marbles in box 3 is 4 5 6 7 8 9. For box 4 due to the pigeonhole principle, there exist 4 marbles with the same colors in box 4 to one of the boxes 1,2,3 (contradiction). c) We can divide like this: Box 1: 1 2 3 4 5 6 Box 2: 1 2 3 7 8 9 Box 3: 1 4 5 7 8 10 Box 4: 3 4 6 7 9 10 Box 5: 2 4 6 8 9 10