Application of Pigeon-Hole Principle to balls in bins. 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.
 A: 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. 
A: 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. 
A: 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.
A: 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.  
