Russian Roulette with a pack of cards
Can the 52 prisoners escape the evil tyrant?
06 July 2016
In a previous blog I described the puzzle of the evil tyrant and the two Black Queens.
Here’s another puzzle in the same vein*. It’s more convoluted than the Black Queens, but if you like probability challenges it’s worth getting your head around it.
This time, fifty-two people have been captured by an evil tyrant who has locked them in a room. (Where would puzzles be without evil tyrants?)
The number of prisoners gives the tyrant an idea.
"I like Russian Roulette" says the tyrant. "Today, I am going to play a version of it, using two packs of playing cards. One pack has red backs, the other blue." He shuffles the red pack, and deals one card to each of the 52 prisoners.
"I will now shuffle the blue pack of cards and deal them out face down in a line on a table in the room next door. We will call that room the blue room," he says.
"I am going to release each of you in turn into the blue room. You can turn over any 51 of the 52 cards on the table, and as long as one of the blue cards you turn over is the same as your red card, you go free. But if you don't turn over a card that matches yours..." He cocks his revolver.
"You are not allowed to change the order of the blue cards - all you can do is turn up to 51 of them over. When you leave the blue room, all the blue cards will be turned face down again."
At first glance this version of Russian Roulette doesn't sound too brutal. Each prisoner figures that his chances of survival is 51/52, about 98%. But the chance that the first two prisoners will both survive if they each turn over the blue cards randomly is 51/52 x 51/52. And the chance that all fifty-two prisoners will escape the bullet is 51/52 multiplied by itself 52 times, or [51/52] ^52. That works out at about 36%. So there's little more than a one in three chance that all of the prisoners will escape death. Unless...they can come up with a plan.
There's no sneaky catch here: only one prisoner is allowed in the second room at any time; they can't mark or damage the blue cards, all they can do is turn cards over (in any order). And once the first prisoner leaves the room, no communication of any kind is allowed between prisoners.
Is there a way for the prisoners to improve the chance that they will survive? Remarkably there is. In fact the prisoners can improve their collective survival chance from 36% to an incredible 98%.
Here’s how.
The prisoners agree on a method for numbering the cards in a deck from 1 to 52. The clubs are 1-13, the diamonds 14-26 (so the Ace of Diamonds is number 14, for example) hearts 27-39 and spades 40-52. They also agree to number the blue cards in the blue room: the card nearest the entrance is number 1, through to number 52 at the other end of the line.
Let's suppose the first prisoner's red card is the Queen of Clubs. By the prisoners’ numbering system, this is card number 12. When the first prisoner goes to the blue room, he turns over card number 12. If he's lucky, that will be his card, the Queen of Clubs. But suppose the card he turns over first is the Two of Diamonds instead. That's card 15 by the numbering system, so he next turns over blue card 15. Suppose that's the Four of Hearts - he next turns over card 30. Using this method, the prisoner is moving around a chain of cards that must eventually lead to his own card. If he's really unlucky, there will be a single chain linking all fifty-two cards with his card the last one, but the chance of that happening is 1/52. As long as the longest chain linking cards is not more than 51, the first prisoner and everyone who follows him is certain to escape. So the chance that at least one prisoner will be shot is the same as the chance that there is a chain of cards that is 52 long, which (you may have to trust me here) is 1/52, which means the probability that they will all survive is 51/52, or 98%.
This is far from obvious and you may well need to draw a diagram to follow it (I did - but I don't have a diagram facility on this blog).
Anyway, I hope this proves helpful next time you're captured by an evil tyrant.
POST SCRIPT
Martin S Taylor emailed me to point out a possible flaw in this cunning strategy. What if there IS a chain of 52 cards? If this does happen, then not only the first prisoner but every single other prisoner will die, too. I have a solution. It's unlikely that the rooms will be fully sound-proofed, so the sound of a gunshot will be audible to the prisoners in the red room. If they hear the first prisoner being shot, it means there is a chain of 52 so they should immediately make a simple change in their strategy. Instead of picking the card that is their number, they should start on a different card (any card will do), and then follow the chain. This will ensure they don't go around the full chain to get to their own card.
* My thanks to Colin Wright for pointing me to the original version of this puzzle which involves selecting 50 boxes out of 100.