7
$\begingroup$

The Great Houdini is performing again! Everybody wants to see the famous magician and the magic show is sold out. Today Houdini shows the following sophisticated trick:

  • A guy from the audience carefully shuffles a deck of $52$ cards ($13$ spades, $13$ hearts, $13$ clubs and $13$ diamonds), and hands the deck over to Houdini's assistant.
  • The assistant then repeats the following step $52$ times: He looks at the top card (of course without showing it to Houdini), and puts it face-down on the table. Houdini guesses the suit. Then the assistant flips the card over and reveals it to everybody (including Houdini). Then the step is repeated.

Houdini's goal is of course to make as many correct guesses as possible. A predecessor puzzle showed us that without cheating Houdini will only predict $13$ cards correctly (in the worst case). Today, however, Houdini and his assistant indeed are cheating:

The backsides of the cards are not perfectly symmetric. The assistant has two different ways of putting down every card, and hence may communicate to Houdini one bit of information per card.

Question: Is there a cheating strategy for Houdini and his assistant that guarantees Houdini to make (a) at least $27$ correct guesses (b) at least $32$ correct guesses (even in the worst possible case)?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ How could we possibly stop houdini from guessing wrong each time he guesses while there are at least three suits in the game? $\endgroup$
    – user10001
    Mar 15, 2015 at 20:59
  • $\begingroup$ so the assistant only knows 1 card at a time? Or is he allowed to look through the deck without changing the order of cards? $\endgroup$
    – Novarg
    Mar 16, 2015 at 11:05
  • $\begingroup$ The assistant only knows 1 card at a time. $\endgroup$
    – Gamow
    Mar 16, 2015 at 12:22
  • $\begingroup$ in this case he can only "predict" 26 cards(in the worst possible case) $\endgroup$
    – Novarg
    Mar 16, 2015 at 12:43

5 Answers 5

Reset to default
10
$\begingroup$

Here's a proof that 26 right answers is optimal for the worst case.

The adversary splits the deck into 13 packets of four cards of different suits, and stacks them on top of each other. Houdini, of course, knows this, and this restriction can only help Houdini.

Without loss of generality for the worst case, Houdini's strategy is deterministic, and the adversary knows it and can pick cards dynamically against it. So, the adversary knows what suit Houdini will guess if his assistant transmits 0, and same for 1.

For the first two cards of the four in the packet, the adversary chooses neither of those two suits Houdini might guess. The remaining two he can't prevent this way. This limits Houdini to 26/52 cards right.

Improve this answer
$\endgroup$
1
  • $\begingroup$ To clarify, this proof works even if the assistant and Houdini use their knowledge of previously seen cards. Consider 4 consecutive cards consisting of S,H,C,D after some 4k turns. Before looking at the next card, the assistant must assign 0 to some of these suits and 1 to the others (possibly using memory). Now there must be two suits which get the same bit and Houdini would infer only one of them (when that bit is transmitted), so that the adversary can use the other. When there are three suits left, the same idea works. $\endgroup$
    – Aravind
    Mar 18, 2015 at 11:58
5
$\begingroup$

I will be happy to be proved wrong, but I believe that Houdini can always guarantee to get 26 cards correct, but can't guarantee any more.

A simple strategy to achieve 26 would be for the assistant to 'transmit' a 0-bit for each red card and a 1-bit for each black card - and Houdini chooses "Hearts" or "Spades" for 0- and 1- bit respectively.

But

even if the assistant could determine (but not alter) the order of the shuffled deck and transmit all 52 bits of info to Houdini right at the start of the performance, I don't think that is sufficient for Houdini to guarantee 32 correct guesses with arbitrary deck order.

Improve this answer
$\endgroup$
1
  • $\begingroup$ That strategy guarantees exactly 26, and never better. There are other strategies where you usually do better than 26, and easily to 32, but, if we are only considering worst case, then I guess none of that matters. $\endgroup$
    – JLee
    Mar 16, 2015 at 1:33
3
$\begingroup$

you have other information as well: the cards that have already been flipped. Houdini can get the 52nd card right regardless of the hint from the assistant. Perhaps he can also get the 51st card right if the one bit of information helps to distinguish between two possible remaining cards. For example, you could signal red/black and if what remained was a red and a black card, you would get the last two right for sure.

I think the 27 right strategy is to signal red/black with the extra win coming from knowing the last card since that is the only card left.

Without memorizing the entire deck you also have "the most recent card that was turned over" to work with. You could signal higher/lower suit value from that, for example.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Yes, this strategy works, but it not necessarily on the last card. It is at the point that the last black card, or the last red card, whichever comes first, is drawn. It does guarantee 27. But I don't see any way to guarantee more than that. $\endgroup$
    – JLee
    Mar 16, 2015 at 14:47
  • $\begingroup$ Who said you got 26 until then? $\endgroup$
    – JNF
    Mar 16, 2015 at 17:27
  • 1
    $\begingroup$ I don't think you can guarantee 27. Consider if you have used the R/B strategy up as far as the last 4 cards, choosing H for R and S for B, and have 24 correct so far with one each of H,D,S,C left in the pack. No point in changing strategy yet, so you can still get the next card wrong (guessing H when the D is 'played'). Now you have 3 cards H, S, C left - you need to get them all right to guarantee a score of 27. But no 1-bit strategy can uniquely identify one of 3 cards. True - you can always identify the last 2 cards correctly, but that only guarantees score of 26. $\endgroup$
    – Penguino
    Mar 16, 2015 at 20:17
  • $\begingroup$ @Penguino Yes, that is correct. Thanks for the example. It help me understand. $\endgroup$
    – JLee
    Mar 18, 2015 at 13:23
2
$\begingroup$

Assign the values $\frac{1}{2}$ to spades, $\frac{1}{3}$ to hearts, $\frac{1}{4}$ to aces and $\frac{1}{5}$ to hearts.

When the assistant sees the card we assign the following value to the card: the number of cards of the suit of that card that have not been flipped plus the value of the special suit of the card. So for example, if the first card is of hearts it has a value of $13.2$.

The dealer uses the following stategy:

She only places the card in position $1$ if that card has the suit that has the highest value at that point in time.

If a card is placed in position $1$ then Houdini guesses the suit with the highest value and obviously gets it right. If the card is in position $2$ Houdini guesses the suit with the second highest value, and might get it right.

This strategy always guarantees $26$ correct guesses and most times it does better. But it can sometimes get exactly $26$ correct guesses.

Improve this answer
$\endgroup$
1
$\begingroup$

(a) at least 27 correct guesses

27 answers is guranteed if assistant use 1 way for red suits and other way for black suits, where Houdini always guessed Hearts for red and Clubs for black, with the last card as a giveaway. Let's call this rule27

(b) 32 correct guesses

Here's my attempt for 32 correct guesses, I do not know how to test it and couldn't come up with a formula:

Both Houdini and the assistant have to remember the last 3 cards revealed. Assistant then perform the following on the next card:

Put the next card down in a different way (say tilt it a bit) only if the following applies:

a) If the suit on the next card appears twice or more in the last 3 cards

b) If the suit on the next card match the color of the first appeared suit in the last 3 cards, or it does not appears in the last 3 cards

(We can create a similar rule for the first 3 cards, but let's ignore it for now.)

Now, for Houdini:

Case a) - same suit appears twice or more in last 3 cards:
- The next card is tilted, Houdini will know what's the next suit for sure.
Case b) - the next card's suit matches the first of the 3 cards appears, or it's the forth suit:
- The next card is tilted, Houdini will know what's the next suit for sure.

Here's some stat:

  • There are 22 combinations possible with the 3 previous cards.
  • There are 18 combinations with a suit appears twice or more.

So, what if the card is place normally?
we apply rule27 on the color that appears least on the previous 3 cards.

The attempts here is to have no more than 2 consecutive normal placement for the next card, which results in 2/3 of correct guess, or 32/52 guesses correct.

I feel like I am missing something but not sure, I am more than happy to discuss or have me proven wrong!
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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