Is this a correct proof of pigeonhole principle?

O

Ozma

Junior Member
Joined
Oct 14, 2020
Messages
78
Pigeonhole principle: "If [imath]n+1[/imath] or more objects are placed into [imath]n[/imath] boxes, then at least one of the boxes contains two or more objects".

Proof. Suppose by contradiction that [imath]n[/imath] boxes contain exactly one object. Then [imath]n+1[/imath], [imath]n+2[/imath], ..., [imath]n+k[/imath] objects , with [imath]k\ge1[/imath] integer, must fill [imath]n+1[/imath], [imath]n+2[/imath], ..., [imath]n+k[/imath] boxes respectively. This contradicts the hypothesis that there are [imath]n[/imath] boxes."

Could this work?
 
I would use contrapositive statement which is If each pigeonhole contains at most one pigeon,
then there are at most n pigeons. This is easily seen to be true.
 
Ozma said:
Pigeonhole principle: "If [imath]n+1[/imath] or more objects are placed into [imath]n[/imath] boxes, then at least one of the boxes contains two or more objects".

Proof. Suppose by contradiction that [imath]n[/imath] boxes contain exactly one object. Then [imath]n+1[/imath], [imath]n+2[/imath], ..., [imath]n+k[/imath] objects , with [imath]k\ge1[/imath] integer, must fill [imath]n+1[/imath], [imath]n+2[/imath], ..., [imath]n+k[/imath] boxes respectively. This contradicts the hypothesis that there are [imath]n[/imath] boxes."

Could this work?
Click to expand...
Can you please state exactly what you are trying to prove by contradiction?
For example, if p=>q, then what are you trying to prove?
 
Hi Steven G, thanks for the help. I am trying to prove that the negation of "at least one of the boxes contains two or more objects" leads to a contradiction. So I'm trying to prove (as you said) that "each box contains at most one object" leads to a contradiction. I hope now is clearer.
 
Ozma said:
Hi Steven G, thanks for the help. I am trying to prove that the negation of "at least one of the boxes contains two or more objects" leads to a contradiction. So I'm trying to prove (as you said) that "each box contains at most one object" leads to a contradiction. I hope now is clearer.
Click to expand...
You should explicitly state your assumption in the beginning -

Only one object in every available slot.​

Otherwise, there is no contradiction!!
 
Thanks Subhotosh Khan, isn't it tacit when I say "[imath]n[/imath] boxes contain exactly one object" because in the hypotheses I say that there are [imath]n[/imath] boxes? Sorry but English is not my first language, so maybe I am missing something here.
 
Ozma said:
Thanks Subhotosh Khan, isn't it tacit when I say "[imath]n[/imath] boxes contain exactly one object" because in the hypotheses I say that there are [imath]n[/imath] boxes? Sorry but English is not my first language, so maybe I am missing something here.
Click to expand...
Yes - you can have 3 pigeons in one box and 2 boxes empty......
 
Oh OK, now I got it. I thought that "placed in [imath]n[/imath] boxes" meant that we are excluding the possibility of empty boxes. Now is all clear, thanks again :)
 
You must log in or register to reply here.
Top