Question

7. Give a proof by contradiction that for any subset S of 26 cards from a 52 card deck ( a 52 card deck is composed of 4 suits of 13 cards each), there is a suit such that S has at least 7 cards of that suit. This is an application of the pigeonhole principle.

Answer 1

For easy reference let us assusme the suit cards are A, B,C,D

Lets us assume a worst case scenario to prove by contradiction.

Lets divide this into two sets: Ours is Set A, and Set B is other remaining

For a certain suit cards say A, assume we have only 6 cards in our set, then the other set contains 7

Similarily for B we have 6 cards in out set A and & in set B

So for now in total Set A has 12 cards and Set B has 14 Cards.

Similarily for suit card C assume we have only 6 cards and , the remaining 7 are sent to set B

Now the total in Set A is 18 where as in set B is 21.

So the remaining is Suit Card D:

The Set B can hold only 5 more cards and those belong to Suit Card D,

where Set A cand hold 7 cards of Suit Card D, hence proving the assumption