GATE CS 2000 Q1.1 — Combinatorics: Counting, Recurrence Relations, Generating Functions

This problem can be solved using the Pigeonhole Principle (PHP).

A standard deck of $52$ cards has $4$ suits (Spades, Hearts, Diamonds, and Clubs). Here, the $4$ suits act as the pigeonholes ($k = 4$), and the cards dealt act as the pigeons ($N$).

We want to find the minimum number of cards $N$ to guarantee that at least $3$ cards belong to the same suit.

Worst-Case Analysis:

• To avoid having $3$ cards of the same suit, we can deal at most $2$ cards from each of the $4$ suits.
• The maximum number of cards we can deal without satisfying the condition is: $$\text{Max cards} = 2 \times 4 = 8 \text{ cards}$$
• Dealing any additional card (the $9^{\text{th}}$ card) will force at least one suit to have $3$ cards.

Using the Pigeonhole Principle Formula:

We want the minimum $N$ such that:

Solving for the minimum integer $N$:

Thus, the minimum number of cards to be dealt is $9$.