Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Say I shuffle and deal a hand of thirteen cards. How can I apply the pigeonhole principle in these cases:

  1. The hand has at least four cards in the same suit
  2. The hand has at exactly four cards in some suit
  3. The hand has at least five cards in some suit
  4. The hand has exactly one suit containing four or more cards

I have problems in which to assign holes and pigeons to, can anyone help?

share|improve this question
1  
Your question isn't clear. I'm sure you can prove 1 using pigeonhole principle but for 2,3 and 4 I don't see how the principle is applicable. 2,3 and 4 need not be true for a randomly dealt hand. –  svenkatr May 20 '11 at 6:41

2 Answers 2

up vote 3 down vote accepted

For the first question, let the four suits be the holes, and the thirteen cards be the pigeons. This is because each time you deal a card of a certain suit, it is like putting a pigeon in a certain hole. The hole fills up with each pigeon, just as the number of cards fill up with each dealt card of a certain suit. By the pigeonhole principle, you are assigning $13$ discrete objects into $4$ containers, so one container must hold at least $\lceil 13/4\rceil=4$ objects.

This makes intuitive sense, for suppose you consciously tried to assign your cards so that no suit had at least four cards in the hand. You could have at most $3$ cards of the same suit for each suit, but in doing so, you would only be able to assign $3\cdot 4=12$ cards. Then the $13^\text{th}$ card must push one of the suits over, so that you have at least $4$ four of the same suit.

For the other cases, the principle doesn't apply. Take the second option for example. You could be dealt $5$ hearts, $3$ diamonds, $3$ clubs, and $2$ spades. You can show the pigeonhole principle does apply in the other cases be finding counterexamples.

share|improve this answer
    
Thanks for the explanation –  meiryo May 20 '11 at 13:39

You can apply the pigeonhole principle to case 1: can you fit thirteen pigeons into four holes each with space for three pigeons?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.