Guessing the Suit
I recently published my new favorite math problem:
A deck of 36 playing cards (four suits of nine cards each) lies in front of a psychic with their faces down. The psychic names the suit of the upper card; after that the card is turned over and shown to him. Then the psychic names the suit of the next card, and so on. The psychic’s goal is to guess the suit correctly as many times as possible.
The backs of the cards are asymmetric, so each card can be placed in the deck in two ways, and the psychic can see which way the top card is oriented. The psychic’s assistant knows the order of the cards in the deck; he is not allowed to change the order, but he may orient any card in either of the two ways.
Is it possible for the psychic to make arrangements with his assistant in advance, before the latter learns the order of the cards, so as to ensure that the suits of at least (a) 19 cards, (b) 23 cards will be guessed correctly?
If you devise a guessing strategy for another number of cards greater than 19, explain that too.
If the psychic is only allowed to look at the backs of the cards, then the amount of transmitted information is 236, which is the same amount of information as suits for 18 cards. This number of guesses is achievable: the backs of every two cards can clue in the suit of the second card in the pair. This way the psychic can guess the suits of all even-numbered cards in the deck. So the problem is to improve on that. Using the info from the cards that the psychic is permitted to turn over can help too.
The problem is from the book Moscow Mathematical Olympiads, 2000-2005. The book and Russian blog discussions provide many different ideas on how to guess more than half of the deck.
Here is the list of ideas.
Idea 1. Counting cards. If you count cards you will know the suits of the last cards.
Idea 2. Trading. As we discussed before, the psychic can correctly guess the suits of even-numbered cards. By randomly guessing the odd-numbered cards she can correctly guess on average the suits of 4.5 additional cards. Unfortunately, this is not guaranteed. But wait. What if we trade the knowledge of the second card’s suit for the majority suit among odd-numbered cards?
Idea 3. Three cards. Suppose we have three cards. Three bits can provide the following knowledge: the majority color, plus the suit of the first and of the second cards in the majority color. Thus, three bits of information will allow the psychic to guess the suits of two cards out of three.
Idea 4. Which card. Suppose the assistant signals the suits of even-numbered cards. With no loss, the psychic can guess the even-numbered card and repeat the same suit for the next card. If this is the plan, the assistant can choose which of the two cards to describe. Which card of the two matches the psychic’s guess provides an additional bit of information.
Idea 5. Surprise. Suppose we have a strategy to inform the psychic about some cards. Suppose the assistant deliberately fails on one of the cards. Then the index of this card provides info to the psychic.
I leave it to my readers to use these ideas to find the solution for 19, 23, 24 and maybe even for 26 cards.
Share:
Code:
I’m a new reader to your blog. Do you want us to share strategies in the comments if we come up with them?
25 March 2012, 7:13 pmTanya Khovanova:
Code,
Yes, please, share the strategies.
26 March 2012, 6:50 amCode:
Alright, I have several for 24. I haven’t quite been able to get up to 26, but I’m still thinking about it. Here’s a (24):
3-bits is sufficient to guess 2 out of 3 cards. but you need 1 of those bits before you start the three cards or else you run into problems, so your first card is guessed at random, and that first bit gives the majority color of the next three. Out of the next three, the first bit gives the suit of the first majority color and the second bit gives the suit of the second card in the majority color. The third bit feeds into the next group of three, telling the majority color. I do 7 groups of three, so including the first card, that’s 1+3*7 = 22 cards so far. Out of the 21 cards in threes, you will get 14 normally, but here is where I use a surprise. On one of the seven (or potentially not at all, representing 000), I screw up the second suit for the majority color. This gives three extra bits at a lose of 1 card, so out of the first 22, I only get 13 correct, but I get 3 surprise bits and 1 bit coming from the last card in the last 3 card set, so 4 extra bits.
For the next four cards, each card provides 1 bit of it’s own, and I use up the 4 bits (1 on each card) to guess each of them correctly. Thus we guess the next 4 out of 4, bringing us up to 17 out of 26. For the next eight cards, I randomly guess the first card, but use its bit to start another chain of 3 cards, this time only 2 in a row. I use the extra bit from the three chain to guess the remaining card of the eight with its own bit, too. Thus, I don’t get the first 1, get 4 out of the next 6, then get the last one correct. That brings us up to 22 out of 34.
Now for the last two, if we’ve been counting cards, then we know there are two suits left. If they are the same, we guess both on the spot and get both right. If they are different, then one of them must be first, so for each of the 6 different situations with two suits, we decide on a bit meaning which one comes first out of the two suits. Thus, we can use our 35th card’s bit to guess what it is, then we know what the last suit is for the 36th card, bringing us up to 24 out of 36.
Is there already a notation for referring to these strategies? My description of where I’m using what technique and where I’m getting bits from can get a *bit* unwieldy.
26 March 2012, 2:43 pmFifteenth Linkfest:
[…] Guessing the Suit (beneath the fluff, there are very interesting questions about information coding here) […]
2 April 2012, 9:18 amDavid Reynolds:
Finally, I came up with a solution for 25 cards. It is a valid solution as it meets all of the constraints of the problem, but it is not a very good solution as I don’t believe any two humans could actually pull it off due to the complexity. There would be an enormous amount of memorization required. Here’s a clue to my technique. Others have pointed out that the psychic can remember the cards that he has seen and by elimination know the last two cards. The assistant can give a clue so he then knows the order of the last two. Think of this as the assistant letting him know which permutation of the remaining cards is the correct order. Now extend that beyond two cards. Careful to keep in mind what the psychic knows and when he knows it. I had to write a computer program to validate the permutation mappings that I used.
My question is, is there a 26 card solution? You don’t have to reveal it, just let us know if it exists, please.
9 April 2012, 1:20 pmTanya Khovanova:
David, there is a 26 cards solution.
9 April 2012, 3:07 pmanonimnystefy:
How can the assistant signal the suits?
17 February 2013, 5:24 amTyler:
Here’s two different strategies, which can get you 23 and 24, respectively.
The ‘three cards’ idea will let you guess 23 cards easily every time. First two cards are random guesses, then the next 34 are all guessed correctly 2 out of 3 times using exactly the system you described in Idea 3:
a) Card 1 Up => Majority color of cards 3,4,5 is RED. Otherwise, majority color of cards 3,4,5 is BLACK.
b) Card 2 Up => The first card in 3,4,5 which matches the majority color is a HEART (if red) or a SPADE (if black). Otherwise, it’s a DIAMOND or a CLUBS.
c) Card 3 Up => The second card in 3,4,5 which matches the majority color is a HEART (if red) or a SPADE (if black). Otherwise, it’s a DIAMOND or a CLUBS.
So if you get (up, down, up) orientations for cards 1,2,3; you’d guess DIAMOND for card 3.
If card 3 is a DIAMOND:
–guess HEART for card 4
–if card 4 is a HEART:
—-guess SPADE or CLUBS for card 5
–else, card 4 is a SPADE or CLUBS:
—-guess HEART for card 5 (guaranteed correct)
done
else, card 3 is a SPADE or CLUBS:
–guess DIAMOND for card 4 (guaranteed correct)
–guess HEART for card 5 (guaranteed correct)
done
Then the orientations for cards 4,5,6 encode a similar decision tree for cards 6,7,8, and so on. Card number 36 you absolutely know, because of card counting. So you know 2 out of every 3 of cards #3 through 35, and 1 card 36. That’s (2/3)*(33) + 1 = 23.
But we can do better.
We can get 24 cards with Idea # 4. Idea #4 is to guess that the odd cards are the same as the even card before them, and the assistant will use the fact of whether the encoded suit is found at the odd or even card as an extra bit of information. So card 1,2 encodes card 2or3 and gives extra bit X; card 3,4 encodes card 4or5 and gives extra bit Y, and card 5,6 encodes card 6 and XY encodes card 7. That’s 5 out of 7 cards, using the bits of info we can get from cards 1 through 6.
Using info from cards 1,2,3,4,5,6 we can get 5 correct guesses for cards 1 through 7.
Using info from cards 7,8,9,10,11,12 we can get 5 correct guesses for cards 8 through 14.
13,14,15,16,17,18 gives 5 correct guesses for cards 19 through 25.
19,20,21,22,23,24 gives 5 correct guesses for cards 26 through 32.
The last four cards, 33, 34, 35 and 36, we can just encode them all with the 8 bits from cards 25 through 33. That’s 5+5+5+5+4 = 24 cards total. Yay!
28 December 2013, 3:08 amJonathan:
Hello, new reader of this blog so apologies for responding to an entry from so long ago, but this problem grabbed my attention and it took me several days before I’d found a way to assure 26 cards. I’ve not seen an answer posted, so here’s my way to reach 26 (and 25, which is considerably simpler). Rather wordy I’m afraid.
We start with some notation. Describe a position by a triplet (x,y,z) where x is the number of guaranteed hits (that is, correctly identified cards), y is the number of used lives (incorrectly identified cards) and z the number of binary bits of information we have accumulated, not including the visible bit on the top card. So the initial position is (0,0,0) and after one guess we’re inevitably on (0,1,1). We’re trying to get to 26 hits at the cost of 10 lives, so (26,10,0).
At any moment I call the top face down card a, the next card b, then c, d etc.
Tanya notes a method to gain a hit and a bit at the cost of a life, which I call the “2 card trick”: use a bit in hand plus card a’s bit to encode the suit of card a or b, the psychic predicts this suit twice, getting one right and one wrong, and the assistant can encode a bit of information based on which of a or b is correct, plus we have b’s bit. (If a and b happen to have the same suit we can pick up two hits, no loss, and continue with the algorithm as though this good fortune had not occurred, which can only be advantageous.) A 2 card trick takes us from (x,y,z) to (x+1,y+1,z+1).
The “3 card trick” is a 2 card trick followed immediately by using the bits on b and c to encode c’s suit. This would take us to (x+2,y+1,z). Effectively the 3 card trick sacrifices a life to gain two hits, leaving bits unchanged. We could perform nine 3 card tricks consecutively to get from (0,1,1) to (18,10,1), then use the last bit to get to (19,10,0), but this is some way off our target.
At this point it’s worth mentioning a useful measure of progress which I call the “count”. The count of a position is: hits + bits – 2*lives. We start off on (0,0,0) with count 0, after one move on (0,1,1) the count is down to -1. We’d like to reach (24,10,0) because if the psychic has counted suits she can deduce the last two cards to score 26. This position has count 24+0-2*10 = 4, so we need to increase the count by 5. The 3 card trick doesn’t change the count, so (19,10,0) still has count -1. We need techniques to increase the count. A few are available of which I will only use two, the first of which we use at the start.
From (0,1,1) perform four 3 card tricks, and deliberately introduce an error on one of them; the choice of which of the four can encode two bits of information. In that erroneous 3 card trick we can introduce the error in four ways (encoding two more bits of information). To spell that out: there are 3 ways the bits on b and c could incorrectly identify the suit of c, and the bit in hand plus bit a could encode either of the two suits on neither card a nor b (and the choice of which suit returns us the bit). The four types of error create two more bits, thus generating a total of four bits from one error in the four 3 card tricks (plus we still have the bit from the last trick making 5 bits in total). This takes us from (0,1,1) to (7,6,5).
(7,6,5) has count 7+5-2*6=0, so we’ve increased the count by 1. We don’t have enough lives to repeat this sequence so need another way to improve the count, more efficient in lives, and the most efficient way I know I call the “3 bit trick”.
As its name suggests, the 3 bit trick requires we have 3 bits in hand (or more). We will combine these 3 bits with the bits on cards a, b and c to encode the suits of a, b and c, but before doing so (as the assistant) look ahead to cards d and e. If either one (or both) of these is a heart we encode the suits for a, b and c correctly. The psychic can pick up 3 hits for a, b and c, then guess hearts for d and e for another hit (and a miss).
If, on the other hand, neither d nor e is a heart, we identify one of a, b or c incorrectly. Which of the three cards is incorrect provides sufficient information to identify which of the three non-heart suits card d could be. Also, there are three ways to incorrectly identify the suit of the erroneous card, which gives enough information to encode card e. The psychic can thus get two hits on card a, b and c, and pick up two more for d and e, along with the bits on those cards.
With either path the psychic gains 4 hits for the cost of one life and one bit. A bargain which increases the count by one.
From (0,1,1) it would be possible to perform six 2 card tricks and four 3 bit tricks to reach (21,10,2) and so to (23,10,0),with count 3. This is not quite enough to guarantee 26 hits, but is a reasonably easy way to reach 25 hits.
Instead, from (7,6,5), left after the four 3 card tricks, we perform three 3 bit tricks to reach (19,9,2).
From (19,9,2) we could play to (21,9,0) or (20,10,3), that is six cards left either with one life or with 3 bits. However, even with careful suit counting, it is not possible to guarantee 26 hits with either of these. For example, to solve a suit partition of 2,2,1,1 (such as CCDDHS) I believe we need 1 life plus 1 bit, or 2 bits plus T (where T is a three-way piece of knowledge) which is about half a bit more than 3 bits. Either way we can’t quite make 26.
Instead, from (19,9,2) we will use the two bits to encode cards a and b, but before doing so look ahead to the last 5 cards. If all 4 suits are present in the last 5 cards then we encode a and b correctly. The psychic gets a and b correct and arrives at (21,9,0), 6 cards remaining, and knows (from the absence of error) that all 4 suits will be present in the last 5 cards.
Alternatively, if only 3 or fewer suits are present in the last 5 cards, we make an error in encoding one of a or b. Which of a or b is wrong encodes a bit, and the three ways to get it wrong a T, leaving (20,10,1+T), 6 cards remaining, and the psychic will know (from the presence of an error) that 3 or fewer suits will be in the last 5 cards.
Either way, this is sufficient information to reach 26 hits. The detail fragments into cases. These are best understood by working backwards from the end of the pack to work out the minimum information needed to solve the various suit partitions with increasing numbers of remaining cards.
But, as example, if the psychic (having carefully counted suits) finds herself facing the last 6 cards with suit partition CCDDHS in position (21,9,0), she knows there must be 4 suits left after the next card. Therefore the next card must be one of Clubs or Diamonds, and this can be encoded on the current top card. This might leave, for example, the split CCDHS and she still has one life left. She guesses clubs: if correct she has a life and a bit which is more than enough to get home; if incorrect she has a bit to play with CCDH (for example). This can be resolved with no lives and 1 bit.
If the psychic faced CCDDHS with 1 bit plus T, she knows only three suits must be left after the next card, so the current card is either Hearts or Spades, which can be encoded in one bit, leaving her facing CCDDH (for example), still with 1 bit + T. We use the T, and might be left with CCDH and 2 bits, but as noted previously we only need 1 bit to resolve this.
So 26 cards is possible.
9 July 2018, 6:09 pm