# Another Information Theory Riddle

The following nice riddle is a quote from the excellent, free-to-download book: Information Theory, Inference, and Learning Algorithms, written by David J.C. MacKay.

In a magic trick, there are three participants: the magician, an assistant, and a volunteer.

The assistant, who claims to have paranormal abilities, is in a soundproof room. The magician gives the volunteer six blank cards, five white and one blue. The volunteer writes a different integer from 1 to 100 on each card, as the magician is watching. The volunteer keeps the blue card. The magician arranges the five white cards in some order and passes them to the assistant.

The assistant then announces the number on the blue card.

How does the trick work?

• I saw a variant on this where five cards were chosen from a standard deck of 52. The assistant chooses one card, then orders the other four, which are passed to the magician, who announces the card the assistant chose. This one is harder because there are only 24 orders and 48 remaining cards. Where do you get the other bit? And the cards cannot be turned upside down. – Ross Millikan May 18 '13 at 3:41
• @RossMillikan, did the assistant pass the cards with her left hand or right? – vadim123 May 18 '13 at 3:55
• @vadim123: No, it wasn't that. The magician doesn't see the assistant. – Ross Millikan May 18 '13 at 3:59
• Seriously though, the extra bit is passed by choice of which card is the mystery card. The assistant can make sure that its suit is represented 0, 2, or 4 times among the other cards. – vadim123 May 18 '13 at 4:00
• @vadim123: it is a little harder, as if the suits of the original cards were SSSHH and the assistant passed SSHH the magician couldn't tell that from SSHHH, but the concept is correct. If out of every 5 cards you agree which one will be chosen, that gives $\frac {\log 5}{\log 2}$ added bits, which is better than 2. As I recall, it works for decks of 120 even. – Ross Millikan May 18 '13 at 4:16

The five cards are uniquely identified by their numbers (low to high). There are $5!=120$ possible orderings for the five cards, which is more than enough to encode the number on the sixth card. In fact, by orienting the cards carefully, there are 4 ways to orient each card and still make a pile (180 degree rotation, turn upside down), there could be $4^55!=122880$ possibilities. I'd only try this variation with a lot of practice, though.

• How can we encode a binary (?) integer from permutations? – user76568 May 18 '13 at 2:37
• @Dror, the simplest way is using lex ordering on the permutations; see Andre's solution for details. – vadim123 May 18 '13 at 2:49
• Shouldn't it be $4^55!$? – Alraxite May 18 '13 at 5:17
• @Alraxite, whoops you're right – vadim123 May 18 '13 at 5:19

The actual numbers written on the white cards don't matter, let's call them, in increasing order, $C_1,C_2,\dots,C_5$. There are $5!$ permutations of $\{1,2,\dots,5\}$, enough to encode all the numbers from $1$ to $120$.

The code (for $120$) could go as follows. If $C_1$ is the top card, then the hidden card is in the range $1$ to $24$; if it is $2$, the hidden card is $25$ to $48$, and so on. Then the range identified by the top card is narrowed down by considering the next card. And so on. With some practice the "reading" would be quick.

• Another way to think about this would be 1 + (zero-indexed position of largest number) * 24 + (zero-indexed position of second largest number) * 6 + ... – mowwwalker May 18 '13 at 7:37

Using @vadim123 's orientation trick, you can encode 2 bits of information per card, regardless of the number written on them and the ordering of the cards. $100<2^7$, so only 3 cards + $Boolean(Sorted)$ suffice for the encoding. :P

I wonder what is the encoding that absolutely minimizes the "resource utilization"... (I wish I had the rep. to start a bounty) :P

• it's important to be careful with orientation. What if the volunteer writes $99$ which looks like $66$ upside down? Need to mark one edge of the card in some way in those cases. – vadim123 May 18 '13 at 3:17