A box contains red, green, blue, and white balls, 111 balls in all. If you take out 100 balls without looking, then there will always be 4 balls of different colors among them. What is the smallest number of balls you must take out without looking to guarantee that among them there will always be balls of at least 3 different colors?
Problem
Source: Tournament of towns, Junior B-Level paper, Fall 2004
Tags: combinatorics unsolved, combinatorics
25.12.2004 16:00
Xixas wrote: A box contains red, green, blue, and white balls, 111 balls in all. If you take out 100 balls without looking, then there will always be 4 balls of different colors among them. This condition means that thre are at least 12 balls of each color. Therefore, if we take 88 balls then it is impossible that we have at most two colors. On the other hand, if there are 12 red, 12 blue, 12 green and 75 white balls then we can choose 87 balls of two colors and for any 100 balls we have all four colors.
25.12.2004 16:03
There must be at least 12 balls of each colour, otherwise if there are fewer than 12 balls of a particular colour, you can select 100 balls of the other 3 colours. Hence it suffices to take out at most $111-2 \times 12+1 = 88$ balls. To show that you must take out at least 88 balls, consider the case where there are 12 red, green and blue balls each.
26.12.2004 00:33
Great minds are colliding Pierre.
26.12.2004 08:26
That's right