Pigeonhole problem

306 Views Asked by At

I'm struggling with this problem for a while now, and I just can't figure it out.

Prove: Let $n_1, n_2, . . . , n_t \in \mathbb{N}^+$
If $n_1 + n_2 + . . . + n_t-t + 1$ Objects are laid in t
Pigeonholes then there's at least one $i \in \{1, . . ., t\}$
so that the i-th pigeonhole has at least $n_i$ objects in it

1

There are 1 best solutions below

4
On BEST ANSWER

Suppose that every pigeonhole has at most $n_i-1$ objects; so there are at most $(n_1-1)+...+(n_t-1)=n_1+...+n_t-t$ objets, hence a contradiction.