# Balls and boxes pigeonhole problem

One has $60$ boxes and many (one colored) balls with $8$ different colors. In every box one puts $3$ balls with different colors. Must there exist (at least) two boxes with the same three colored balls?

If one puts $3$ balls with different colors each in a box, we must find first how many combinations we can have from $8$ different colors choosing 3 each time. That is $(\frac{8}{3}) = 56$ different combinations of colors, which means that there are exactly $4$ boxes with the same color (according to the pigeonhole principle).

I just want to check if my way of thinking is right?

• Your way of thinking is not correct. Calling $1,2, \dots , 8$ the colours, it could be possible that there are two boxex with $1,2,3$ , two boxes with $2,3,4$ , two boxes with $3,4,5$, two boxes with $4,5,6$, and all other boxes have exactly one of the other 52 combinations. – Crostul Mar 28 '16 at 6:35

## 1 Answer

Your explanation is partially correct.

There are $\binom{8}{3} = 56$ ways of selecting three of the eight colors. Since there are $60$ boxes, this means that there must be at least two boxes containing the same combination of three colors.

However, we cannot conclude that there are four boxes containing the same combination of colors, as you seem to be stating. Crostul has provided you with an example in the comments. One extreme case is all $60$ boxes contain the same three colors. The other extreme is that all $56$ color combinations are used, with four of them being used twice. Is that what you meant?

To guarantee that there are at least three boxes containing balls with the same combination of three colors, we would require that there be at least $2 \cdot 56 + 1 = 112 + 1 = 113$ boxes. If we had only $112$ boxes, we could use every color combination exactly twice.

The strong form of the pigeonhole principle states that if $k$ objects are to be placed in $n$ boxes, then the number of boxes that must contain the same number of objects is $$\left\lceil \frac{k}{n} \right\rceil$$ where $\lceil x \rceil$ is the least integer greater than or equal to $x$. In our case, $k = 60$ and $n = \binom{8}{3} = 56$, so we are guaranteed at most $$\left\lceil \frac{60}{56} \right\rceil = 2$$ boxes that contain the same combination of three colors.