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

a) Solution:
The deck of cards in a set is =52

Since there are 4 suits, if we only select the 4 cards then it is possible that we get 2 cards of each suit. So 4 is not enough to guarantee at least 2 cards of the same suit. However, if we select 5 cards then the Pigeonhole Principal tells us that we will get at least [5/2]=2 cards of the same suit. So 5 is the least we can select to guarantee at least 2 cards of the same suit.At least two are the same suit is 5.
b) Solution:
Assume that any couple of numbers are substitued by its difference to its symmetrical as follows {1,2,...n/2,n/2+1,...,n}={n−1,(n−2)−2...,(n/2−n/2),1,...,n−1}
That means the set becomes; {5,3,1,1,3,5}
The probability of picking up any number is 1/6
The probability of picking up any number added up to the previous not giving 7 is the probability of not chosing the same number again, that means 1/6∗1/4
The probabilty of picking up a third number not equals to both picked up ones is 1/6∗1/4∗1/2 until this moment nothing left in the set to be picked up satisfying the condition so picking a forth number is of probabilty 1/6∗1/4∗1/2∗0=0.