1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why is $m_{s+1}\geq k+1$? $\endgroup$ – Annisar Nov 17 '13 at 15:43
  • $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Nov 17 '13 at 15:46
  • $\begingroup$ Thank you, brilliant proof. $\endgroup$ – Annisar Nov 17 '13 at 16:07
  • $\begingroup$ @Kamil: You’re welcome. $\endgroup$ – Brian M. Scott Nov 17 '13 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.