GATE CSE 2000 | Question: 1.1

Question

The minimum number of cards to be dealt from an arbitrarily shuffled deck of $52$ cards to guarantee that three cards are from same suit is

• A. $3$
• B. $8$
• C. $9$
• D. $12$

Comments

@Akash 15 yeah,understood thanks

---

Hope it will help ...

---

If you want to guarantee that at least one box contains r objects, how many objects do you need?

Suppose there are k boxes. 
INITAILLY WE ARE AVOIDING
To avoid having r objects in any box, each box can contain at most:

r−1

Therefore maximum objects without reaching r:

k(r−1)

So one more guarantees r:

k(r−1)+1​

objects.

now in this question  we are having  4 SUITS WHICH MEANS 4 DIFFERENT BOXES AND to guarantee that three cards are from same suit is 
first avoid: k(r-1)
then +1 guarantees ...means k(r-1)+1  so this much enough to guarantee.
 

Answer 1

There are $4$ sets of cards. So, up till $8$ cards there is a chance that no more than $2$ cards are from a given set. But, once we pick the $9$$^{th}$one, it should make $3$ cards from any one of the sets. So, $(C)$ is the answer.

Comments

may be in first 3 attempt we get same(suits) card and question is asking about minimum.

then A (3) is best choice

---

minimum in worst case.

---

But it will not guarantee  that three cards are from same suit. Only Picking 9 or more ( 9 or10 or ......or 52) will guarantee that three cards are from same suit.

Minimum of( 9 ,10, 11...52)= 9, So, 9 is the answer(minimum number of cards to be dealt to guarantee that three cards are from same suit)

Answer 2

As suggested above also

apply pigeon hole, 4 holes (suits)

n pigeons(no of cards to be drawn)

floor [(n-1)/p] +1=3

floor[(n-1)/4]  =2

(n-1)/4  >= 2

n>=9

minimum 9 cards must be picked

Answer 3

Any corrections or questions  to my solution are welcome

 

Comments

I could not understandem logic behind to apply pigeonhole principle. But this technique help me lot.

Answer 4

Can this question be solved by calculating expectation:
Expectation of getting three cards from same deck->

E(x) = 13*(13/52) + 12*(12/51) + 11*(11/50)
       =  8.49 => 9 cards

Hence 9 is the answer.
Is it correct?

Comments

@shikhar May you please explain your approach more? I find it's correct use of "Expectation".

Answer 5

An easier way to think it as of worst case outcomes that is each time we take the card it is from different suit.

We know that there are 4 suits.

Let,

Heart= $H$

Spade= $S$

Diamond= $D$

Club= $C$

So the possible withdrawal sequence  (alternating/worst case)

 $HSDCHSDC\displaystyle$__ (this 9th card will make 3 cards of same suit.)

Therefore option C

Comments

nice one for understanding

Answer 6

Let Min Number of cards be N.

 

Given,

No of holes (holes) = 4 (since there are 4 suits in pack of 52 cards)

Required no of cards (R) = 3 (since 3 cards of same suit required)

Using Generalized Pigeon Hole,

$\left \lceil \frac{N}{holes}\right\rceil$ = R

$\left \lceil \frac{N}{4}\right\rceil$ = 3

So minimum N satisfying above equation is 9 ( since $\left \lceil \frac{9}{4}\right\rceil$ = 3).

Hence Option C is correct.