1

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

Seirios
  • 33,157
Sebastian Hatl
  • 55

1 Answers1

3

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.

Seirios
  • 33,157
  • this problem should be provable – Sebastian Hatl Jan 16 '13 at 12:24
  • @SebastianHatl: I don't understand, where is your problem? – Seirios Jan 16 '13 at 12:42
  • I'm trying to understand the proof, are you proving by using contradiction? if so, how does it prove it.. I don't think I understand what you did there :I – Sebastian Hatl Jan 16 '13 at 12:53
  • @SebastianHatl: Indeed, it is a proof by contradiction. The negation of "there exists $i$ such that the $i$-th pigeonhole contains at least $n_i$ objets" is "for all $i$ the $i$-th pigeonhole contains at most $n_i$ objects". Then, the total number of objets is the addition of the number of objets in each pigeonhole, that is at most $(n_1-1)+...+(n_t-1)$; but this quantity is smaller than the actual number of objets. – Seirios Jan 16 '13 at 12:57