[Guest]

Here's a nice problem I've found on another site, hope it's not posted here before.

Two prisoners are given a chance to escape jail by winning a card game which works as follows:

The guard randomly selects five cards out of a normal deck (52 cards, no jokers) and gives them to prisoner #1 (say, Alyson).

She must then give four of the cards, one at a time, to prisoner #2 (Brian).

After receiving the four cards, Brian must then determine what Alyson's 5th card is.

They're given the day prior to discuss strategy, but while the game is going on they can communicate only with the cards. Alyson can't bend the cards or mark them somehow, and she can't delay giving cards to Brian in order to make some kind of timer signal.

To be generic, if she thinks of any way to communicate with Brian other than the cards, then the guard will think of a foolproof way of stopping it.

So, what's their game plan?

(PS. It's an evil jail and the two prisoners are fighters for righteousness, so we want them to escape. )

[akaslickster]

closes one of her eyes and hand on her heart for a jack of hearts to show him.

[Guest]

Does Brian have to guess both the card number and suite?

[Guest]

When you have five cards in your hand, you must have at least two of one suite. The last card you give to your partner should be the same suite as the card you keep to yourself.

[Brandonb]

As PMan said, give the repeated suit card last that matches the card that is kept.

Then there are four ways that a card can be handed:

Value of 1 =Lengthwise face down

Value of 2 =Sideways face down

Value of 3 =Lengthwise face up

Value of 0 =Sideways face up

If a low card is kept, then all that is needed is to hand the cards by their given values.

Even if the repeat cards are maxed-out in value as a king&queen(lets say of hearts), then "Alyson" keeps the queen (value of 12) and hands all the rest (4) of the cards Lengthwise face up, with the last card being the king of hearts. This would mean a value of 12 and a suit of H.

[Guest]

That is Brilliant! Is that the answer?

[Guest]

P Man is on the right track, one of the cards should be a 'suit' card that tells Brian what suit the card your holding is. Let this be the first card to give to Brian. The next three cards gives the number of the last card, but first we need to define a total order on the cards: Let A of Clubs = 1, 2 of C=2, ... , K of C=13, A of Diamonds = 14, 2 of Diamonds = 15, ... , A of Hearts=27, ... , A of Spades=40, K of S=52 so that every card has a number 1-52. Note that there are 3! ways to permute 3 cards or 6 ways. Since the cards are ordered one of 3 cards has a lowest value, one is in the middle, and one has the highest value.

If Alison gives Brian the cards in the order:

lowest, middle, highest then add 1 to the suit card

lowest, highest, middle then add 2 to the suit card

middle, lowest, highest then add 3 to the suit card

middle, highest, lowest then add 4 to the suit card

highest, lowest, middle then add 5 to the suit card

highest, middle, lowest then add 6 to the suit card.

Note that addition is mod 13 (not on the total order of the cards, but just on the ordering of a suit, also we're letting A = 1 and K = 13 = 0)(edit:actually i just realized that the addition mod 13 still works on the total ordering of the cards if its the same as above);ex. if Alyson gives Brian a 10H and the next three cards tell Brian to add 5, then she must be holding a 2H.

There is a catch... with this system it does matter which suit card Alyson gives to Brian. ex: If she had handed him the 2H first instead of the 10H this system would fail.

Nevertheless, carefully choosing the suit card you should always be able to communicate which card you're left holding. This is because if x, y belong to the set {0,1,...,12} then either x-y<=6 or y-x<=6.

Edited May 5, 2008 by randomnumber

[Guest]

Well, this might be similar to what Brandonb wrote, but basically we can use a binary counting system (card face up or face down) to get the value of the card, and then to get the suit we can hand one of the four cards to Brian sideways.

ex) ace = 1; king = 13, in the binary system.

if the card is face up brian will add the number to the total.

1st card = 1

2nd card = 2

3rd card = 4

4th card = 8

and just one of the four cards should be handed sideways to denote the suit. (maybe alphabetically?) ex)

1st card = clubs

2nd card = diamonds

3rd card = hearts

4th card = spades

so the Q of spades would be

1) longways face down (not a club and don't add 1)

2) longways face down (not a diamond and don't add 2)

3) longways face up (not a heart, add 4)

4) sideways face up (it's a spade, add 8)

so the total 0 + 0 + 4 + 8 = 12 (which translates to a Q), and it's a spade

Hopefully i explained that in a way that makes sense to you guys. Lemme know if you can think of any improvements!

[bonanova]

Prisoner 1 chooses a card to keep.

The choice must be made in a way that enables the other four cards to signal the suit and value of the kept card.

Choose a card of the same suit as one of the other four and pass it by agreement either first or last to signal the suit.

The other three cards must now signal the value of the kept card.

It cannot be presumed that these cards have a known suits or values; they can only be rank ordered.

That is, of the three cards, one will be the highest and another the lowest.

There are six distinct sequences for passing the high and low cards.

So Prisoner 1 can tell Prisoner 2 a suit and a number from 1 to 6, which seems insufficient to identify a card.

There is one more piece of information: the value of the suit-signaling card.

Now there is enough information to uniquely identify the held card.

[Brandonb]

Prisoner 1 chooses a card to keep.

The choice must be made in a way that enables the other four cards to signal the suit and value of the kept card.

Choose a card of the same suit as one of the other four and pass it by agreement either first or last to signal the suit.

The other three cards must now signal the value of the kept card.

It cannot be presumed that these cards have a known suits or values; they can only be rank ordered.

That is, of the three cards, one will be the highest and another the lowest.

There are six distinct sequences for passing the high and low cards.

So Prisoner 1 can tell Prisoner 2 a suit and a number from 1 to 6, which seems insufficient to identify a card.

There is one more piece of information: the value of the suit-signaling card.

Now there is enough information to uniquely identify the held card.

"one will be the highest and another the lowest" is not necessarily the case. They could all be the same number, or two of them could be the same. So for this to work there would also need to be a suit ranking order. At that point there could be a conflict b/w the "suit signal" card and what order the cards would need to be handed in order to signal correctly.

[bonanova]

The combination of suit and value is sufficient to establish a rank order: equal value "ties" broken by suit preference.

Think of two poker hands with no pairs or flush.

One hand will be the winning hand based on higher ranking high card.

[Brandonb]

The combination of suit and value is sufficient to establish a rank order: equal value "ties" broken by suit preference.

Think of two poker hands with no pairs or flush.

One hand will be the winning hand based on higher ranking high card.

right, ties would be broken, but lets say the suit hierarchy is S,H,D,C. Also, the suit signal card is decided to be the last one given.

**values(4=highest, 1=lowest)/card # are as follows**

1,2,3=Ace

1,3,2=Two

2,1,3=Three

2,3,1=Four

3,1,2=Five

3,2,1=Six

You are dealt 7H,7S,QS,QC,3D

You would have to pick the 7S or the QS (lets say you keep the 7S)

the hierarchy of the remaining cards is QS, QC, 7H, 3D (though the QS would have to be held for last)

So to signal six it would be QC, 7H, 3D. Then QS to give suit. (signaling the 6S, not 7S)

Where do you go from there to show that a 7S is the card being held? Maybe I'm not fully understanding your method.

[Guest]

right, ties would be broken, but lets say the suit hierarchy is S,H,D,C. Also, the suit signal card is decided to be the last one given.

**values(4=highest, 1=lowest)/card # are as follows**

1,2,3=Ace

1,3,2=Two

2,1,3=Three

2,3,1=Four

3,1,2=Five

3,2,1=Six

You are dealt 7H,7S,QS,QC,3D

You would have to pick the 7S or the QS (lets say you keep the 7S)

the hierarchy of the remaining cards is QS, QC, 7H, 3D (though the QS would have to be held for last)

So to signal six it would be QC, 7H, 3D. Then QS to give suit. (signaling the 6S, not 7S)

Where do you go from there to show that a 7S is the card being held? Maybe I'm not fully understanding your method.

you can't hold the 7S, you need to pick the QS to keep; using your method, then give QC, 3D, 7H to signal 'add 5', then give 7S...Brian understands he needs to add 5 to 7S to get...8S, 9S, 10S, JS, QS! ...assuming i'm understanding how you order cards for least to greatest...my earlier post just gives a straight enumeration of the cards 1-52

[bonanova]

right, ties would be broken, but lets say the suit hierarchy is S,H,D,C. Also, the suit signal card is decided to be the last one given.

**values(4=highest, 1=lowest)/card # are as follows**

1,2,3=Ace

1,3,2=Two

2,1,3=Three

2,3,1=Four

3,1,2=Five

3,2,1=Six

You are dealt 7H,7S,QS,QC,3D

You would have to pick the 7S or the QS (lets say you keep the 7S)

the hierarchy of the remaining cards is QS, QC, 7H, 3D (though the QS would have to be held for last)

So to signal six it would be QC, 7H, 3D. Then QS to give suit. (signaling the 6S, not 7S)

Where do you go from there to show that a 7S is the card being held? Maybe I'm not fully understanding your method.

Begin with the value of the suit-signaling card and add 1-6 to it.

That tells you which of the [at least] two same-suited cards to pass.

[Guest]

Well done, guys, I'm REALLY impressed!!!

I struggled for days to find the solution and you did it in few hours!