Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.