Maths Olympiad Prep

Library / /35 of 53

Combinatorics Difficulty 6.9 National olympiad Prove it Vietnam

A student divides 3030 marbles into 55 boxes labelled 1,2,3,4,51, 2, 3, 4, 5 (there may be a box without marble).

a. How many ways are there to divide marbles into boxes (two ways are different if there is a box with different number of marbles)?

b. After dividing, this student paints those marbles by a number of colors (each marble have one color, one color can be painted for many marbles), such that there does not exist 22 marbles in the same box, having a mutual color and from any 22 boxes, it is impossible to choose 88 marbles painted in 44 colors. Prove that for every division, the student must use at least 1010 colors to paint the marbles.

c. Find a division so that the student can use exactly 1010 colors to paint the marbles that satisfies the conditions in question b).

Solution

a.
It is well known that there are (n+k1k1)\binom{n+k-1}{k-1} ways to divide nn marbles into kk boxes. In this case, the answer is (344)\binom{34}{4}.

b.
Let mm be the number of colors, x1,x2,,xmx_1, x_2, \dots, x_m be the number of boxes containing marble with color 1,2,,m1, 2, \dots, m respectively. We now count the number of tuples (A,B,C)(A, B, C), where A,BA, B are the boxes having marbles with the same color CC.

On the one hand, since every two boxes have in common at most 33 colors, thus the number of pairs is at most 3(52)=303\binom{5}{2} = 30.
On the other hand, the number of pairs is S=i=1m(xi2)S = \sum_{i=1}^{m} \binom{x_i}{2}. Since in each box, there are at most one marble in each color, we get that i=1mxi=30\sum_{i=1}^{m} x_i = 30. By the Cauchy-Schwarz inequality, we have
S=12(i=1mxi2i=1mxi)12(302m30). S = \frac{1}{2} \left( \sum_{i=1}^{m} x_i^2 - \sum_{i=1}^{m} x_i \right) \geq \frac{1}{2} \left( \frac{30^2}{m} - 30 \right).
Hence,
900m3060m10. \frac{900}{m} - 30 \le 60 \Leftrightarrow m \ge 10.

c.
Consider the following table.

| Box | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|-----|---|---|---|---|---|---|---|---|---|----|
| 1 | × | × | × | × | × | × | | | | |
| 2 | × | × | × | | | | × | | × | × |
| 3 | × | | | × | × | | | × | × | × |
| 4 | | × | | × | | × | × | × | | × |
| 5 | | | × | | × | × | × | × | × | |

It is a direct checking that the table satisfies the requirements. ☐

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.