Take the 2-minute tour ×
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.

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|improve this question
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.