Application of Pigeon-Hole Principle to balls in bins.

Question

Given $n$ balls placed in $m$ boxes, prove that if $n < \frac{m(m-1)}{2}$ then at least two boxes have same number of balls in them.

Answer 1

This is easier without the pigeonhole principle. Consider any arrangement of balls in $m$ boxes such that no two boxes have the same number of balls. Then at most one box can be empty, requiring $0$ balls. At most 1 additional box can have just one ball; the rest ($m-2$ boxes) have at least two balls. At most 1 box can have 2 balls, and so on. So the $m$ boxes must contain at least $0+1+2+\ldots + (m-1) = \frac{m(m-1)}{2}$ balls.

Answer 2

The sum of $m$ distinct non-negative integers is $\geq 0 + 1 + 2 + \dots + (m-1)$. One line of proof is to list the integers in increasing order.

Answer 3

The statement is equivalent to "if no two bins have the same number of balls, then $n\ge m(m-1)$."

Let $a_0$ be the number of bins with $0$ balls, $a_1$ the number with $1$ ball, and so on. Then $$ n=\sum_{j=0}^\infty ja_j. $$ If no two bins have the same number of balls, then $a_j=0$ or $1$ for every $j$. In that case, exactly $m$ of the numbers $a_j$ equal $1$. Use this to get the lower bound on $n$.

Alternatively, if one wants to apply the pigeonhole principle explicitly, one can do the following. Label the balls with the numbers $1$ through $n$. Label the bins with the numbers $1$ through $m$. One is free to carry out the labeling of bins so that bin $2$ has at least as many balls as bin $1$, bin $3$ has at least as many balls as bin $2$, and so on. Assume this has been done. Let $b_j$ be the occupancy of bin $j$. By assumption $b_1\le b_2\le\ldots\le b_m$. Define $[1,k]$ to be the set $\{1,2,\ldots,k\}$.

Now there are $\binom{m}{2}=\frac{m(m-1)}{2}$ ways to choose two distinct bins. If the occupancies $b_j$ are all distinct, the we can define the map $f:\{(i,j)\in[1,m]^2\mid j>i\}\rightarrow[1,n]$ by $$ \begin{aligned} f((i,j))=&\text{the label of the $(b_i+1)^\text{st}$ ball in bin $j$, with the balls in bin $j$ ordered}\\ &\text{according to their labels,} \end{aligned} $$ and one can see that $f$ is one-to-one. Now apply the pigeonhole principle with the pairs of distinct bins as the pigeons and the ball labels as the pigeonholes.

Answer 4

The minimum number of balls needed to fill m boxes with different number of balls is

$0 + 1 + 2 + 3 +.... + m-1 = \frac{m(m-1)}{2}$

since $n < \frac{m(m-1)}{2}$, at least 2 boxes must contain the same number of balls.