Explain Pigeonhole principle and Extended Pigeonhole Principle. Show that if 7 colors are used to paint 50 bicycles, at least 8 bicycles will be of same color.

30kviews

written 8.9 years ago by

teamques10 ★ 70k

modified 3.8 years ago by

pedsangini276 • 4.8k

Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 8 Marks

Year: May 2015

discrete mathematics

ADD COMMENT EDIT

1 Answer

4.8kviews

written 8.9 years ago by

teamques10 ★ 70k

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.