## 5 Cards, Choose 4

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

hayaz
Posts: 4
Joined: Sat Sep 01, 2012 3:58 am UTC

### 5 Cards, Choose 4

This is a cute puzzle, though probably not as hard as many that get posted here.

A player is dealt 5 random cards from a deck, and is permitted to pass on some 4 of them to his partner, from which the partner must guess the 5th card. They agree on some kind of code beforehand, but can't communicate during the problem. How do they do it?

The order of the cards passed can be changed (so HK-DJ-SA-C4 is allowed to communicate something different than DJ-SA-HK-C4), but cards may not be turned over, rotated, bent, etc.

If you think the problem is impossible:
Spoiler:
The argument that says "there are only 24 permutations of 4 cards, so you can't possibly map to the other 48" is wrong. The problem isn't to, given 4 cards, be able to arrange them to code for any given card in the deck; it's to take 4 cards from 5 so that the last one can be determined, which is a problem with more information.

Hint:
Spoiler:
You can communicate suit easily via pigeonhole.

Spoiler:
While there are multiple answers, in my code "HK-DJ-SA-C4" communicates "H9", and "DJ-SA-HK-C4" communicates "D5".

Moonbeam
Posts: 292
Joined: Sat Dec 08, 2007 5:28 pm UTC
Location: UK

### Re: 5 Cards, Choose 4

Sandor
Posts: 178
Joined: Sat Feb 13, 2010 8:25 am UTC

### Re: 5 Cards, Choose 4

That thread includes a proof that this is possible with a pack of up to 124 cards (5!+4). After much squinting at Wikipedia (I don't know any graph theory) I've convinced myself of the proof's validity.

So, can anyone come up with a simple method to solve this with more cards - say two packs of cards, one with red backs and one with blue backs (104 cards). The magician would see the front and back of the 4 shown cards, but not see the fifth card at all. Obviously the magician has to call the value, suit, and back colour of the fifth card.

The best I can come up with is a method for 53 cards (full pack plus joker).

 I've now found a method for 66 cards. Hint:
Spoiler:
I used 2 packs of cards, both with 3 suits of 11 cards.
Still trying...

kalakuja
Posts: 43
Joined: Sun Feb 06, 2011 10:15 am UTC

### Re: 5 Cards, Choose 4

This one was great. thank you

Barstro
Posts: 103
Joined: Mon Aug 13, 2012 2:34 pm UTC

### Re: 5 Cards, Choose 4

Sandor wrote:That thread includes a proof that this is possible with a pack of up to 124 cards (5!+4). After much squinting at Wikipedia (I don't know any graph theory) I've convinced myself of the proof's validity.
.

Could anyone dumb-down that proof enough to explain it to me?

As I understand the solution;
Spoiler:
1) Of the five cards, you need to select one card that has another of the same suit

2) In the sequence of 2, 3, 4,... K, A, 2, 3...; the reserved one should be the one to the right, where the gap between the two is smaller (if you have 7h and 9h, choose the 9; if you have 6h, kh, choose the 6)
The Reserved card uses up FIRST card

3) The first card you show to magician is the other card of the same suit to let him know what the suit is
This uses up SECOND card

4) The remaining cards are given a ranking based on number and suit, and arranged accordingly
This allows for 3! steps = 6 steps
The greatest number of cards one can have with at most six steps between them is 13.

A way to get more;
Spoiler:
Ignore suits entirely
1) Of all the cards, choose the two that are closest together
2) Reserve the higher card
3) The lower card is played first
you still have 3! to work with (6)

The greatest number of cards I can come up with while guaranteeing that there will be two within 6 of each other for five cards drawn is 13+13+13+13+12=64 (and I might be six too high on that)

---------------------------------------------------------

Mike Rosoft
Posts: 63
Joined: Mon Jun 15, 2009 9:56 pm UTC
Location: Prague, Czech Republic

### Re: 5 Cards, Choose 4

I see no way how your variant would work.

Spoiler:
I assume that you are pretending that the cards are labeled "1, 2, 3, ..." (rather than with suits and ranks). Well, let's see you get 1, 8, 15, 22, 29 (out of a 35-card deck). No two cards are six or less points apart! (The original solution depended on the choice of the initial card - it helped eliminate all but six possible cards by knowing that a) the hidden card has the same suit and b) the first card and the hidden card are no more than 6 ranks apart [since there are 13 ranks], and the hidden card is the bottom of the pair.

Mike Rosoft

ThirdParty
Posts: 341
Joined: Wed Sep 19, 2012 3:53 pm UTC
Location: USA

### Re: 5 Cards, Choose 4

Sandor wrote:That thread includes a proof that this is possible with a pack of up to 124 cards (5!+4). After much squinting at Wikipedia (I don't know any graph theory) I've convinced myself of the proof's validity.

So, can anyone come up with a simple method to solve this with more cards
Barstro wrote:Could anyone dumb-down that proof enough to explain it to me?

I think I've got a 124-card solution. Not sure if it counts as "simple".

Procedure:
Spoiler:
The cards are numbered "1" to "124" and can be conceptually arranged linearly or in a circle. When talking about the circle, I'll use the terms "left" and "right": "123" is the second card to the right of "121" and the third card to the left of "2". When talking about the line, I'll use the terms "below" and "lowest"; there are four cards below "5", and the second-lowest card which is not in the range "1"-"8" is "10".

Sender: make a list of the 124 cards. Circle the five cards that are in your hand. Do the following until only one circled card remains on the list: choose the circled card on the list with the smallest block of non-circled cards on the list to its left; cross it off the list, and then start crossing off the cards from its right, until the total number of cards that have been crossed off the list is equal to 25 times the number of circled cards that have been crossed off of the list. The last remaining circled card is the card you will reserve. Count the number of cards below it that remain on the list. Call this number N. Encode N as a permutation of the four cards you are not reserving, using a pre-arranged method, and then reveal them in that order.

Receiver: make a list of the 124 cards. One at a time with each of the four revealed cards, cross 25 cards off the list, starting with the revealed card and moving rightward, skipping cards that have already been crossed off. Retrieve N from the permutation of revealed cards, and cross the lowest N cards off the list. Guess the lowest card on the list which has not yet been crossed off.
Example:
Spoiler:
Sender's hand contains "1", "6", "50", "90", and "100". Sender makes his list and circles these five cards. "6" is the card with the smallest block of cards to its left, so sender crosses off cards "6"-"30" from his list. Now "100" is the card on the list with the smallest block of cards to its left, so sender crosses off cards "100"-"124" from his list. Now "1" is the card on the list with the smallest block of cards to its left, so sender crosses off cards "1"-"5" and "31"-"50" from the list, notices that an extra circled card has gotten crossed off, and so also crosses off "51"-"75". Now the only circled card remaining on the list is "90", so that will be the reserve card. There are 14 cards below it remaining on the list, so N = 14. Since N%4+1 = 3, the sender starts by revealing the third-lowest non-reserved card from his hand, i.e. "50". Since (N/4)%3+1 = 1, the sender next reveals the lowest non-reserved card remaining in his hand, i.e. "1". Since (N/12)%2+1 = 2, the sender next reveals the second-lowest non-reserved card remaining in his hand, i.e. "100". He then reveals the final non-reserved card remaining in his hand, i.e. "6".

Receiver sees "50", "1", "100", "6", in that order. Receiver makes his list. He looks at "50" and crosses off cards "50"-"74". He looks at "1" and crosses off cards "1"-"25". He looks at "100" and crosses off cards "100"-"124". He looks at "6" and crosses off cards "26"-49" and "75". Now he decodes the permutation: of the last two cards, the first was the second-lowest, so he crosses off the lowest twelve cards on his list ("76" thru "87"); of the last three cards, the first was the lowest, so he does nothing; of the last four cards, the first was the third-lowest, so he crosses off the lowest two cards on his list ("88" thru "89"). The lowest remaining card remaining on his list is "90", so he guesses "90".

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: 5 Cards, Choose 4

The last time I saw this problem was in 2005(ish, may have been 2003 or 4), and I remember proving it using the Marriage theorem as in the linked thread. I recall coming up with an explicit solution for 124 cards (actually any n), I'll see if I can't recreate it. WARNING: Random attempts follow, may not lead anywhere and no effort is made to be concise.

Spoiler:
For 8 cards, chosing 3 and leaving 2, there is a translation invariant solution. Arranging the cards based on the differences between them, and the options are:

(1,1,6) eg cards 1,2,3, (2-1 = 1, 3-2 = 1, 1-3 = -2 = 6 (mod 8))
(1,2,5)
(1,3,4)
(1,4,3)
(1,5,2)
(2,2,4)
(2,3,3)

The pair you leave behind is defined by the difference between the second and first card, so it's a number mod 8, but can't be 0, and has to be obtainable as either a number above, or the sum of a number and the number cyclically to its right (eg 1,2,3 I can leave 1,2 for a difference of 1, or 1,3 for a difference of 1+1, or 3,1 for a difference of 6 = -2 mod 8, etc). Many things seem to work, just being greedy requires only 1 correction:

(1,1,6) -> 1
(1,2,5) -> 2
(1,3,4) -> 3
(1,4,3) ->4
(1,5,2) ->7
(2,2,4) ->6
(2,3,3) ->5

And there's lots of room to fiddle, eg 1 and 2 can be switched, as can 3 and 4, 3 and 7, 2 and 6, etc etc. So we should look for a nice way that might generalize to higher n. Will this approach even generalize? We're looking at ordered partitions of n!+k-1 into k positive parts, modulo cyclic translation, and comparing that to ordered k-1 subsets of n!+k-1 modulo translation. Are those even the same size (I'd guess so, but only because I think a translation invariant solution exists)

Not sure if this is going anywhere.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.