3

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.

Kasper-34
  • 99

1 Answers1

3

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.

Calvin Lin
  • 68,864
  • 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? – Kasper-34 Aug 15 '13 at 06:31
  • 1
    @Kasper-34 For the generic way, just replace everything with the corresponding $n_i$ and $n_i - 1$. – Calvin Lin Aug 15 '13 at 06:47