Spring 2018, problem 66

Two boxes contain between them 65 balls of several different sizes. Each ball is white, black, red or yellow. If you take any five balls of the same color, at least two of them will always be of the same size(radius). Prove that there are at least three ball which lie in the same box have the same color and have the same size(radius).

Comments

amdilley
3 years ago

By the pigeon hole principle (PHP) we know there are at least 17 balls of the same color among the 65 (16 * 4 + 1 = 65). WLOG, assume there are 17 red balls. Since there are 2 boxes, again by PHP we know one box must have at least 9 red balls. Among these 9, assume no three were the same color (if they were we're done). Take 5 from the 9. Then 2 of them are of the same radius, r1. Take these 2 and set them aside and then grab 2 more balls from the remaining pile of 4 to replace them. Again we have 5 balls so 2 of them must have the same radius, r2. Take these 2 and set them aside, again replacing them with 2 more from the remaining pile of 2. Having 5 balls we know 2 have the same radius, r3. Take these and set them aside and replace them with the last 2 balls. Since we have 5 we know 2 have the same radius, r4. Our 9 red balls have radii r1, r1, r2, r2, r3, r3, r4, r4, r5 where r1, r2, r3, r4, r5 are all distinct values. However r1, r2, r3, r4, r5 is a group of 5 balls which contradicts the condition that 2 of them must have the same radius. Therefore our assumption is wrong and there must be three of the same size radius.

lucianosantos
3 years ago

We have $65$ balls and $4$ colors. Then $65\div 4=16.25$ ,and so there is a set $C$ with at least $17$ balls of the same color. Let $c=|C|\geq 17$. On the other hand, in each set of balls with the same color there can only be, at most $ 4 $ different radius, because " any five balls of the same color, at least two of them will always be of the same size(radius)" . Let $r$ be the number of different radius in $C$.If all balls have the same radius consider $r=1$. As $r\leq 4$ then $c\div r \geq 17\div 4=4.25$, we have that at least 5 balls of the set $C$ have the same radius. So at least $3 $ of these balls are in the same box.