mathematics - The Great Houdini's awesome card guessing trick (2)

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)?

Answer

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.