3
$\begingroup$

Let $n_1,n_2,\ldots,n_t$ be positive integers. Show that if $n_1+n_2+\cdots+n_t-t+1$ objects are placed into $t$ boxes, then for some $i$, $i = 1,2,\ldots,t$, the $i$th box contatins at least $n_i$ objects.

I don't understand what "$i$th box contains at least $n_i$ objects" means. I've tried doing a specific example to see what is going on and this is what I came up with.

$n_1$ = 12 , $n_2$ = 8, $n_3$ = 34, $n_4$ = 11

$t$ =4

The sum of my $n_1,n_2\ldots,n_t$ elements is 65 then I subtract 4 and add 1 to get 62 objects. I then cacluclate $\left\lceil\frac{62}{4}\right\rceil$ = 16. So, does that mean that at $i$ = 3 my $n_3$ box contains at least 16 objects because it contains 32 objects?

Any hints on constructing the proof itself is also appreciated.

$\endgroup$
3
$\begingroup$

It means that either the first box as at least 12 items, or the second box has at least 8 items, or the third box has at least 34 items, or the fourth box has at least 11 items.

If none of these statements are true, then there are at most $11 + 7 + 33 + 10 = 61$ items, contradicting the assumption that there are 62 times.

$\endgroup$
  • $\begingroup$ That makes so much more sense! Could you give me a hint on how to write that in the generic way to prove it as well? $\endgroup$ – Kasper-34 Aug 15 '13 at 6:31
  • 1
    $\begingroup$ @Kasper-34 For the generic way, just replace everything with the corresponding $n_i$ and $n_i - 1$. $\endgroup$ – Calvin Lin Aug 15 '13 at 6:47

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.