Question

Use pigeonhole principle to prove the following (need to identify pigeons/objects and pigeonholes/boxes): a. How many cards must be drawn from a standard 52-card deck to guarantee 2 cards of the same suit?Note that there are 4 suits b. Prove that if four numbers are chosen from the set {1, 2, 3, 4,5,6), at least one pair must add up to 7.

Answer 1

Explanation:

a. The pidgeons/objects here are the cards and the pigeonholes/boxes here are the suits. We are trying to draw cards/pidgeon that have the same suits/pidgeonholes. Since there are 4 different suits, we need to draw at least 5 cards to guarantee 2 cards of the same suit.

b. Let there be 3 holes, which represent 3 pairs of number with sum equals to 7. They are:

- {1,6} as 1 + 6 = 7

- {2,5} as 2 + 5 = 7

- {3,4} as 3 + 4 = 7

You can see that if we pick randomly 4 numbers, we will always end up with 2 numbers in the same hole, which means there will be at least a pair and add up to 7.