Skip to main content
OlympiadHQ

Browse · MathNet

Print

VMO

Vietnam counting and probability

Problem

A student divides marbles into boxes labelled (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 marbles in the same box, having a mutual color and from any boxes, it is impossible to choose marbles painted in colors. Prove that for every division, the student must use at least colors to paint the marbles.

c. Find a division so that the student can use exactly colors to paint the marbles that satisfies the conditions in question b).
Solution
a. It is well known that there are ways to divide marbles into boxes. In this case, the answer is .

b. Let be the number of colors, be the number of boxes containing marble with color respectively. We now count the number of tuples , where are the boxes having marbles with the same color .

On the one hand, since every two boxes have in common at most colors, thus the number of pairs is at most . On the other hand, the number of pairs is . Since in each box, there are at most one marble in each color, we get that . By the Cauchy-Schwarz inequality, we have Hence,

c. Consider the following table.
Box12345678910
1××××××
2××××××
3××××××
4××××××
5××××××
It is a direct checking that the table satisfies the requirements. ☐
Final answer
a) C(34, 4). b) At least 10 colors are necessary. c) One valid configuration using exactly 10 colors: Box 1 uses colors 1,2,3,4,5,6; Box 2 uses colors 1,2,3,7,9,10; Box 3 uses colors 1,4,5,8,9,10; Box 4 uses colors 2,4,6,7,8,10; Box 5 uses colors 3,5,6,7,8,9.

Techniques

Counting two waysRecursion, bijectionColoring schemes, extremal argumentsCauchy-Schwarz