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.

You've been dealt five cards from a standard deck, and you wish to communicate the exact contents of your hand. The catch is that you're only allowed to make utterances of the form "I have an $X$" or "I don't have any $X$s", where $X$ is the name of a rank. How many such statements do you need to convey what's in your hand, and what's the simplest protocol you can use?

share|improve this question
    
What exactly is "the exact contents of your hand"? If you can only mention ranks, you can't differentiate between suits, so "the exact contents of your hand" can't include information about the suits? Also, you can't differentiate between having three queens and two kings and having three kings and two queens when all you can say is whether you do or don't have any queens and kings? Ah -- or are you looking for how to use these utterances as a code unrelated to their English meaning? –  joriki Nov 2 '12 at 3:28
    
@joriki: Yes, you can predesign a protocol under which the choice (and order) of statements should be interpreted. The protocol might be easier to remember, though, if the statements are somewhat related to their English meaning. –  mjqxxxx Nov 2 '12 at 3:42
    
It is a rather different problem if all your statements need to be true. –  Ross Millikan Nov 2 '12 at 3:49
    
@Ross: Yes, that's what I thought at first :-) –  joriki Nov 2 '12 at 3:49
1  
@Ross: Ah, I see. Interesting. I confused being true with being said to convey its truth :-) –  joriki Nov 2 '12 at 4:02

1 Answer 1

There are $\binom{52}5=2598960$ different poker hands, and you have $26$ different utterances to make. Thus you need to make at least $\lceil\log_{26}2598960\rceil=5$ statements.

Here's a simple protocol that almost works and can hopefully be adapted without undue complication. For each card, use its actual rank in one of the five statements, and decide whether to say that you have or don't have that rank according to whether the card is red or black. Since you don't have to convey order, you can use the order of the cards to convey the missing information about the suits. Ideally, if all five cards correspond to different statements, you have $5!=120$ ways of ordering them, and you only need $2^5=32$. However, if you're unlucky, you might have two pairs of identical statements, which would only leave $\binom5{2,2,1}=30$ ways of ordering them, slightly fewer than the required $32$, so you'd have to make an extra rule for encoding a few of these rare cases.

share|improve this answer
    
+1 for giving the lower bound. The log (base $26$) is $4.53$, so you've got wiggle room... I'm not sure you've got a workable factorization yet, though. If the statements need to be true, then the log (base $13$) is $5.76$: then you need at least $6$ statements and have less flexibility. –  mjqxxxx Nov 2 '12 at 4:05

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.