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?
Poker communication problem
-
0@joriki: In a sense, that is the point of asking for the simplest protocol-to our human brains a statement with the purpose of conveying its truth is simpler. – 2012-11-02
1 Answers
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.
-
0+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. – 2012-11-02