A simple counting and restricting the case from Vietnam National Olympiad 2021

Question

Abstract

This problem is apparently not difficult and I managed to solve it, but I think it is just nice to share it on MSE. This might be considered one of the most "give away" problem (if not the most) in the entire contest, but the idea to solve it is worth knowing, though.

The contest's over: for another question on it, see here

Problem

Dan is given $30$ marbles to divide in to $5$ boxes, each box consist of a non-negative number of marbles. He then color the marbles such that

1. No marbles of the same box have the same color and
2. For each two boxes, we cannot choose $8$ marbles (in total) from them so that the number of colors chosen is less than or equal to $4$.

Prove that, in order to color the marbles, Dan has to use at least $10$ colors.

Answer 1

1. Note, that numbers of marbles in boxes ordered in descending order can have the following patterns (* means, that this number is irrevelant):

• 10+, *, *, *, *
• 9, 6...9, *, *, *
• 8, 6...8, *, *, *
• 7, 6...7, *, *, *
• 6,6,6,6,6

Of course in the first case the proof is trivial.

1. Note, that considering all marbles within box have different color, the only situation when we have a chance of picking only 4 colors is when we pick 4 marbles from each box.

2. To make sure, that we pick at least 5 colors while picking 4 marbles from 2 boxes each, it's obvious, that second box can't contain more, than 3 colors from the first one. Knowing this it's pretty obvious, that in cases, where the biggest box contains 7-9 marbles, and second biggest contains at least 6 marbles, we have to use at least 10 colors (first box is coloured in at least 7 colors, second one gives us at least 6-3=3 more colors)

3. Now comes the fun part. Assume, that the balls are divided into 5 boxes, 6 marbles each. Assume, that in 2 boxes we've used only 9 colors (according to the previous step, it's impossible to use less colors). Let's take the third box - it's possible to use already existing colors ( 3 new from the second box, a 3 from the first one, that weren't used in the second one). We still have 9 colors, each one used in two boxes.

Now comes the fourth box. Assume, that we've used only the existing colors - we've picked 6 out of them. Each one was previously used in 2 boxes, which gives us 12 matches. According to the pigeonhole principle, there's at least one box with at least 4 matches, which contradicts with the assumption, that there are at most 3 matches between boxes. Therefore it's impossible to color fourth box using only already used 9 colors and we have to introduce one more, tenth color.

QED.