Ask
Login
0
18kviews
State and explain Pigeonhole principle, extended Pigeonhole principle.How many numbers must be selected from the set{1, 2, 3, 4, 5, 6 }to guarantee that at least one pair of these numbers add up to 7?
written 8.9 years ago by gravatar for teamques10 teamques10 ★ 70k modified 3.8 years ago by gravatar for pedsangini276 pedsangini276 • 4.8k

Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 8 Marks

Year: Dec 2014
discrete mathematics
ADD COMMENT EDIT
1 Answer
2
2.5kviews
written 8.9 years ago by gravatar for teamques10 teamques10 ★ 70k •   modified 8.9 years ago

Pigeonhole principle:

If k is a positive integer and k+1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.

Proof: We will prove the pigeonhole using a proof by contraposition. Suppose that none of the k boxes …

Create a free account to keep reading this post.

and 2 others joined a min ago.

ADD COMMENT EDIT
Please log in to add an answer.