# Induction and typical pigeonhole principle

Let $n,\,k,\,r,\,s\in\mathbb{N}$ and $0\leq r,s<n$. We have $nk+r$ objects placed in $n$ containers. Show that we can choose $s$ containers such that there is at least $sk+\min{\{r,\,s\}}$ objects inside in total.

I have tried induction by $n$ (and I look for answer involving induction if this is possible, but all others are welcome). Proof is pretty straightforward (i use pigeonhole principle on set of $n$ containers and then, using assumption for $n-1$ I know that in the rest of containers I can find some $s_0$ such that $s_0k+\min{\{r,\,s_0\}}$), but I have no idea what comes next.

## 1 Answer

For $j=1,\ldots,n$ let $m_j$ be the number of objects in the $j$-th container; we may assume that $m_1\ge m_2\ge\ldots\ge m_n$, and we want to know what the minimum possible value of $m_1+\ldots+m_s$ is. Specifically, we’d like to show that it’s $sk+\min\{r,s\}$.

Suppose that $r\ge s$ and $m_1+\ldots+m_s<sk+s$. Then

$$m_{s+1}+\ldots+m_n>(nk+r)-(sk+s)=(n-s)k+(r-s)\ge(n-s)k\;,$$

so $m_{s+1}\ge k+1$. But then $m_s\ge k+1$, so $m_1+\ldots+m_s\ge s(k+1)=sk+s$, a contradiction. Thus, $m_1+\ldots+m_s\ge sk+s$, as desired.

Now assume that $r<s$ and that $m_1+\ldots+m_s<sk+r$, and argue similarly to get another contradiction, thereby completing the proof of the desired result.

It may help the intuition to realize that the sum $m_1+\ldots+m_s$ is minimal when $m_1,\ldots,m_n$ are as nearly equal as possible, and that this occurs when

$$m_i=\begin{cases} k+1,&\text{if }1\le i\le r\\ k,&\text{if }r<i\le n\;. \end{cases}$$

The desired result follows immediately from this, though I think that it’s at least as easy to prove the desired result directly.

• Why is $m_{s+1}\geq k+1$? – Annisar Nov 17 '13 at 15:43
• @Kamil: Because if it were $k$ or less, we’d have $$\underbrace{m_{s+1}+\ldots+m_n}_{n-s\text{ terms}}\le(n-s)k\;,$$ since each of the $n-s$ terms would be $\le k$. But we know that the sum is greater than $(n-s)k$. – Brian M. Scott Nov 17 '13 at 15:46
• Thank you, brilliant proof. – Annisar Nov 17 '13 at 16:07
• @Kamil: You’re welcome. – Brian M. Scott Nov 17 '13 at 16:10