Prisoner: Cards 2

#1

Same setup as Cards 1.

The game: Prisoner 1 goes into the warden’s office again. The warden shuffles a standard 52 card deck and deals out 5 cards to prisoner 1. Prisoner 1 looks at these cards, gives one back to the warden and places the remaining 4 cards on the table in any order face up. The cards must be placed straight (prisoner 1 can’t try to pass information to prisoner 2 by tilting the cards slightly etc). Prisoner 1 leaves and prisoner 2 enters. Prisoner 2 looks at the 4 face up cards and must guess which card prisoner 1 gave to the warden.

What is their strategy?

1 Like
#2

Hmmm. Well it’s definitely possible.

There are 24 orderings of 4 cards and you need to identify one of 48 cards possible 5th cards. That won’t work. So obviously you need to pick which of the 5 cards you will exclude in such a way that, looking at which cards remain (irrespective of order), P2 can narrow down the choice of possible 5th cards to 24 or less.

So I’m thinking what about rule you might use to pick which 5th card to remove. It can’t be an absolute rule based on number or suit, or at least such a rule would need many cases. As you can make no guarantees about the properties of the cards you draw. So the rule should be relative to the 5 cards you draw. The simplest might be a rule based on their ordering, for example by removing the card with the second lowest value.

I think I’m onto something thinking about cards ordered as ABCDE and looking at 3 card lines A to C, B to D, and C to E. One of these (actually two), will be shorter than 24 cards apart. I need to think more about how P2 might be able to tell which of the 3 lines was chosen.

If it works it definitely wouldn’t be elegant.

#3

So, as there are 5 cards but only 4 suites you can signal the suite of the card by returning one of the duplicated suites (which exists cause pigeon hole) then leave the remaining card of that pair on top. We then have 3 cards left which we could order to sneak in more information, we could pass a number between 1-6 using these by ordering them. So if we could specify the face value of the card using a number between 1 and 6 we’d be done. But there are 13 numbers there which is annoying.

#4

Oh! I see how to sneak that in.

Summary

tl;dr given two numbers 0 <= a < b <= 13 we know that 1 <= | a - b (mod 13) | <= 6 which gives us the rest of the information we need. Spelled out completely:

Following the same line of thought from the previous post.
We will number the cards 0-12 (ace is zero, jack 10, queen 11, king 12). We then agree that the following ordering holds on the suits: diamond < club < heart < spade.

By the pigeon hole principle we know there exist two cards out of the 5, call them A and B, such that A and B have the same suite. Moreover we know that there exists some x with 1 <= x <= 6 such that A = B + x (mod 13). Using the face value combined with the ordering on the suites we know the last three cards can be ordered. Lets call them C, D, E where C > D > E.

If we pass the cards in the order B[CDE] (with CDE in some permutation) our comrade can determine the suite by looking at B. Then because we agreed on our ordering they can determine which card was C, D, and E respectively. Then based on the order of [CDE] our friend can determine the x in the equation A = B + x (mod 13) using this handy table (or whatever pairing we agree on)

CDE => x = 1
CED => x = 2
DCE => x = 3
DEC => x = 4
ECD => x = 5
EDC => x = 6

This explanation feels clunky.

Very nice problem :smile:

1 Like
#5

Brilliant! I love it.

Great idea to use the difference between the cards. That was my inclination but my line idea was too complicated to continue to think about. One thing to add to your explanation is that you must correctly choose which of the two cards will be your A and which will be your B.

#6

Thanks :blush:

Summary

Yeah I tend to get very lazy and just slap a “without loss of generality” on things like that. I’ll clean it up soon™️