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


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.

  • $\begingroup$ this problem should be provable $\endgroup$ – Sebastian Hatl Jan 16 '13 at 12:24
  • $\begingroup$ @SebastianHatl: I don't understand, where is your problem? $\endgroup$ – Seirios Jan 16 '13 at 12:42
  • $\begingroup$ 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 $\endgroup$ – Sebastian Hatl Jan 16 '13 at 12:53
  • $\begingroup$ @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. $\endgroup$ – Seirios Jan 16 '13 at 12:57

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.