Author |
Topic: Guessing Cards Suit (Read 10541 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Guessing Cards Suit
« on: Apr 3rd, 2004, 3:56am » |
 Quote  Modify
|
A magician takes a deck of 36 cards (nine cards of each suit) lying face down. He guesses predicts the suit of the top card, turns it up and puts aside. Then he guesses predicts the suit of the second card, turns it up and puts aside, and so on with the entire deck.
The deck for the trick was prepared by his secret assistant who knows the order of the cards. He uses the fact that the cards in the deck are slightly non-symmetric, and so the magician can distinguish between two possible orientations of every card. The assistant is not allowed to alter the order of the cards, but he can choose the orientation.
What is the best strategy the magician and the assistant should agree upon in order to maximize the number of guaranteed guesses correct predictions?
Source: Moscow Mathematical Olympiad.
Corrected the formulation to (hopefully) avoid confusion.
|
| « Last Edit: Apr 26th, 2004, 12:56am by Barukh » |
 IP Logged |
|
|
|
KarmaBandit
Newbie
Gender:
Posts: 16
|
|
Re: Guessing Cards Suit
« Reply #1 on: Apr 3rd, 2004, 3:37pm » |
Quote Modify
|
No solution, just my initial thoughts:
First, It seems the only information passed to the magician is the bit of info from each card, and the running total of how many cards of each suit have been seen. Is there something else I'm missing?
Second, maybe multiple strategies would be better than a single one, and the first few cards could be used to encode which strategy to use? Since the assistant knows all the cards, he could choose the optimal strategy, and then encode it.
But even with these no doubt amazing insights, the best I can think of stills gets only half of them. Help!
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Guessing Cards Suit
« Reply #2 on: Apr 3rd, 2004, 4:47pm » |
Quote Modify
|
I don't have a better answer yet either, but some numbers to put it in perspective: there are 36!/9!4 [approx] 2.15 x 1019 different arrangements of the cards with regard only to suit. There are 236 [approx] 6.87 x 1010 different messages that the assistant can send by arrangement of card backs. If this is the only means the assistant has of communicating, it is impossible to specify the suit of every card. Working from some very naive assumptions, I get that somewhere between 20 and 24 cards is the maximum possible. But the assumptions were very poor, so this could well be wrong.
I am sure this can be bettered, but I will give the only method I have thought of so far, which is probably KarmaBandit's as well: take the cards two at a time and use the backs to encode a two bit result giving the suit of the second card. In this way you can guarantee 1/2 the deck.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Guessing Cards Suit
« Reply #3 on: Apr 4th, 2004, 7:09am » |
Quote Modify
|
on Apr 3rd, 2004, 3:37pm, KarmaBandit wrote:| First, It seems the only information passed to the magician is the bit of info from each card, and the running total of how many cards of each suit have been seen. Is there something else I'm missing? |
|
You've got it right.
Quote:| But even with these no doubt amazing insights, the best I can think of stills gets only half of them. Help! |
|
You may get 19 cards quite easily.
In fact, I know at least 24 cards are possible, but I still refrain from looking into the solution.
|
|
IP Logged |
|
|
|
asterix
Guest
|
Just a thought for possible improvement, although I think this only improves their odds, not the number of guaranteed guesses. Make more use of the alternate cards.
For instance, plan on guessing black for the first card. Up will mean clubs, down means spades. If that gives the correct answer, then start over, perhaps alternating so that you will assume the next card is red; Up means hearts, down means diamonds. If the next card turns out to be the wrong color, then its orientation plus the next card's orientation will give the suit of the next card.
You could improve that a little more by counting cards and always planning on making the assumed guesses for whichever color is more prevalent (if a lot of blacks turn up at first, you'll be assuming red). It will make things a little more complicated but improve the odds even more if you don't go by color but by whichever two suits are most prevalent (give the suits a priority: clubs, spades, hearts, diamonds: and of the two most common suits, whichever comes first in that list would get the up orientation).
That plus the fact that you always know the last card of the deck should get you above 50%, but I'm not sure it helps on the guaranteed guesses.
|
|
IP Logged |
|
|
|
asterix
Guest
|
Sorry, I tried it out, and in the worst case scenario, it seems my method would still only give you 19 correct.
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Guessing Cards Suit
« Reply #6 on: Apr 24th, 2004, 11:43am » |
Quote Modify
|
on Apr 3rd, 2004, 4:47pm, Icarus wrote:| There are 236 [approx] 6.87 x 1010 different messages that the assistant can send by arrangement of card backs. |
|
It is at most 235, because the last one is always useless.
Starting from there, when the two cards are left of the same suit,
no information is needed, and if they are of different suits, 1 bit is enough, so the last two cards are a given.
When there are 3 cards left, unless they are of 3 different suits, all 3 can be guessed correctly, and if they are, the expected number is 2 2/3, etc.
This does not give us the guaranteed number, though.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Guessing Cards Suit
« Reply #7 on: Apr 24th, 2004, 2:10pm » |
Quote Modify
|
on Apr 24th, 2004, 11:43am, Leonid Broukhis wrote:| It is at most 235, because the last one is always useless. |
|
No, it is useful. The magician sees the back of this card - and gets the information from it, before he makes his final prediction.
The first card, however, may not give any information, unless only the magician and the assistant are allowed to touch the cards, or some other means is in place to assure that the magician will see the deck as a whole in a particular orientation. If the assistant is in some other room, and an uninterested third party carries the deck, he may end up reversing the deck, so the magician has no way of knowing what orientation the card ought to be in for a "yes" bit vs. a "no" bit. If this is the case, the magician and assistant will have to sacrifice one bit of information just to inform the magician of how the other cards should be oriented.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Guessing Cards Suit
« Reply #8 on: Apr 24th, 2004, 9:21pm » |
Quote Modify
|
I also believe that the last card's orientation is irrelevant - having seen all but one card's face, it would be a poor magician who couldn't tell you what that last card was even without the signal...
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Guessing Cards Suit
« Reply #9 on: Apr 24th, 2004, 11:47pm » |
Quote Modify
|
on Apr 24th, 2004, 2:10pm, Icarus wrote:
No, it is useful. The magician sees the back of this card - and gets the information from it, before he makes his final prediction.
|
|
And what exactly he does not know already? The running counts per suit are 9, 9, 9, and 8.
Quote:| The first card, however, may not give any information, unless only the magician and the assistant are allowed to touch the cards, or some other means is in place to assure that the magician will see the deck as a whole in a particular orientation. If the assistant is in some other room, and an uninterested third party carries the deck, he may end up reversing the deck, so the magician has no way of knowing what orientation the card ought to be in for a "yes" bit vs. a "no" bit. If this is the case, the magician and assistant will have to sacrifice one bit of information just to inform the magician of how the other cards should be oriented. |
|
The conditions say nothing about any room or a third party. We can safely assume that the orientation is kept. Why twist the conditions in an unfavorable way?
Let me propose something. As we're trying to find a guaranteed number, let's pretend the assistant has to prepare a deck that happens to be partially ordered: 4 A's in any suit order, 4 K's, 4 Q's, .... so the algorithm would not be able to use any count disparity.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Guessing Cards Suit
« Reply #10 on: Apr 25th, 2004, 6:42am » |
Quote Modify
|
on Apr 24th, 2004, 11:47pm, Leonid Broukhis wrote:| Let me propose something. As we're trying to find a guaranteed number, let's pretend the assistant has to prepare a deck that happens to be partially ordered: 4 A's in any suit order, 4 K's, 4 Q's, .... so the algorithm would not be able to use any count disparity. |
|
I am not sure I understand your proposal. Note that the assistant is not allowed to change the order of the cards...
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Guessing Cards Suit
« Reply #11 on: Apr 25th, 2004, 9:03am » |
Quote Modify
|
on Apr 25th, 2004, 6:42am, Barukh wrote:
I am not sure I understand your proposal. Note that the assistant is not allowed to change the order of the cards... |
|
Therefore the algorithm should work for all arrangements, including the one I've mentioned, in which the number of arrangements of the suffix of the sequence decreases the slowest.
In any case, 235 is greater than 20!/5!4 and less than 21!/5!36!, that is, the magician drops the first 16 cards, doing random guesses but collecting their orientation information, then correctly predicts the last 20 (let's say he has an arithmetic decompressor in his head). As the algorithm must guarantee the number of correctly guessed suits, it must not depend on the actual card sequence, and as they cannot be rearranged, they cannot convey any additional information.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Guessing Cards Suit
« Reply #12 on: Apr 25th, 2004, 9:24am » |
Quote Modify
|
I see...
on Apr 25th, 2004, 9:03am, Leonid Broukhis wrote:| ...that is, the magician drops the first 16 cards, doing random guesses but collecting their orientation information, then correctly predicts the last 20 (let's say he has an arithmetic decompressor in his head). |
|
Are you saying that 20 is the maximum he can correctly guess?
|
|
IP Logged |
|
|
|
Nigel_Parsons
Junior Member
Gender:
Posts: 63
|
|
Re: Guessing Cards Suit
« Reply #13 on: Apr 25th, 2004, 5:56pm » |
Quote Modify
|
The question, as phrased, is complex & misleading. It asks for the number of 'Guaranteed guesses'. If they are guaranteed then they are not guesses (which suggests a lack of knowledge) but predictions.
It is clear that the suit of the final card is guaranteed.
The suit of the penultimate card can also be guaranteed (if two of the same suit are left), or, if two different suits are left, the orientation of the penultimate card shows whether that card is first or second (alphabetically) of the two remaining (i.e. Clubs, Diamonds, Hearts, Spades)
For the forgoing cards, the orientation should merely show 1 of 2 possibilities (e.g. black/red) giving a 50/50 chance of guessing (these are not guaranteed guesses.)
When down to three cards, there are 3 possibilities: 3 of a suit (the magician will get all three), two of one suit (the orientation of the first card will tell if it is the odd one or not, again allowing the magician to get all three) this will leave either two the same (guaranteed) or one of each (orientation shows alphabetical order), or 3 suits. The orientation of the first card will show if it is the single card of one colour giving certaintity if it is or 50/50 otherwise.
The above makes it clear that the orientation can help to provide a better than 50/50 chance for each of the last three cards.
So in the earlier stages the single one bit inference can either be set as "1= black, 2=Red", or 1=choose most likely(i.e the suit with most remaining), 2=choose second most likely.
If there are two equally likely suits, the meaning of the signal changes. 1= choose first in alphabet(of two) 2= choose second. This means both magician and assistant need to keep close count, but it will improve the odds.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Guessing Cards Suit
« Reply #14 on: Apr 25th, 2004, 7:59pm » |
Quote Modify
|
on Apr 24th, 2004, 11:47pm, Leonid Broukhis wrote:
And what exactly he does not know already? The running counts per suit are 9, 9, 9, and 8. |
|
Maybe the assistant could use it tell the magician whether or not his fly is open! 
Okay - my thinking was more than a little fuzzy on that one!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Guessing Cards Suit
« Reply #15 on: Apr 25th, 2004, 11:30pm » |
Quote Modify
|
on Apr 25th, 2004, 9:24am, Barukh wrote:I see...
Are you saying that 20 is the maximum he can correctly guess?
|
|
Of course not. He can correctly guess all 36, but I do not see how more than 20 predictions can be guaranteed. Out of the remaining 16, the expected number of correct guesses is around 4 (slightly higher because of the count disparity), but it does not mean that 24 correct guesses are guaranteed.
What is more interesting is how to get those 20 guaranteed predictions using a simple algorithm.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Guessing Cards Suit
« Reply #16 on: Apr 26th, 2004, 1:19am » |
Quote Modify
|
As there seems to be a confusion in the formulation (I would blame my broken English), I changed it, removing any appearance of word “guess” and using “prediction” instead.
on Apr 25th, 2004, 11:30pm, Leonid Broukhis wrote:I do not see how more than 20 predictions can be guaranteed…
What is more interesting is how to get those 20 guaranteed predictions using a simple algorithm. |
|
There is a fairly simple strategy that guarantees 23 correct predictions (I wish it was mine). Here’s the hint: Out of the first 18 cards, there are at least 5 cards of the same suit.
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Guessing Cards Suit
« Reply #17 on: Apr 26th, 2004, 12:02pm » |
Quote Modify
|
on Apr 26th, 2004, 1:19am, Barukh wrote:There is a fairly simple strategy that guarantees 23 correct predictions (I wish it was mine). Here’s the hint: Out of the first 18 cards, there are at least 5 cards of the same suit.
|
|
Sweet! Isn't it ironic how I would prevent others from making unfavorable assumptions while falling into the same trap myself?  Nobody says the magician has to predict correctly which particular cards' suit he is going to predict correctly.
Here is a correction to the hint: Out of 18 cards, either at least 2 suits have no less than 5 cards, or a suit has at least 6 cards.
You're saying there is a way to pull at least another one?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Guessing Cards Suit
« Reply #18 on: Apr 27th, 2004, 12:11am » |
Quote Modify
|
on Apr 26th, 2004, 12:02pm, Leonid Broukhis wrote:| Isn't it ironic how I would prevent others from making unfavorable assumptions while falling into the same trap myself? Nobody says the magician has to predict correctly which particular cards' suit he is going to predict correctly. |
|
Excellent point  ! But somehow, I didn't think about this at all.
Quote:| You're saying there is a way to pull at least another one? |
|
Yes. I don't know the strategy though.
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Guessing Cards Suit
« Reply #19 on: Apr 27th, 2004, 12:26pm » |
Quote Modify
|
I've spoiled myself some fun by clicking on a link in some search results (in Russian) and by scrolling a little too much, but I've learned that 25 are possible, but the algorithm is much more complex than the one for 24, which is quite ingenious by itself. A hint: out of every three cards, at least two have the same .....
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Guessing Cards Suit
« Reply #20 on: Apr 27th, 2004, 5:14pm » |
Quote Modify
|
Using Leonid's clue:
Two out of every three are the same color (red or black). Start off guessing every card is black and use the back of the card to identify whether it is spades or clubs. As soon as you get one wrong, start guessing the same color for the next three cards. The predominant color in that set of three is identified by the orientation of the last card that was wrong. As others have described the last two in the deck will always be correct (switch strategy at that point).
That should give at least 25 right most of the time, except possibly when you get the first card wrong. In that case, the orientation of the wrong card in the 2nd to last group of three gives one bit, and the back of the 3rd to last card gives a bit: two bits can identify what suit the 3rd to last card, so you correctly guess the final 3 cards.
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Guessing Cards Suit
« Reply #21 on: Apr 27th, 2004, 5:53pm » |
Quote Modify
|
on Apr 27th, 2004, 5:14pm, SWF wrote:
That should give at least 25 right most of the time, except possibly when you get the first card wrong. In that case, the orientation of the wrong card in the 2nd to last group of three gives one bit, and the back of the 3rd to last card gives a bit: two bits can identify what suit the 3rd to last card, so you correctly guess the final 3 cards[/hide].
|
|
In that case, your first group of 3 cards starts at the 2nd card, and the last group only has 2 cards, so you lose a bit of information and still get only 24.
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Guessing Cards Suit
« Reply #22 on: Apr 27th, 2004, 8:10pm » |
Quote Modify
|
I see. For some reason, I was assuming the 3rd to last card was the minority suit in the final group of three, and ignored that it could be 4th or 5th from the end.
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Guessing Cards Suit
« Reply #23 on: Apr 30th, 2004, 1:18pm » |
Quote Modify
|
I have an idea that might lead to a solution for 25 cards, but I could not figure out the implementation. In the solution for 24 cards, the assistant must lie in his prediction for one out of the first 16 cards that could be predicted correctly (that is, are of the current dominant suit). This way one prediction is lost, but 4 bits are gained. theoretically allowing to recoup the loss and guess one more card.
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Guessing Cards Suit
« Reply #24 on: Apr 30th, 2004, 7:31pm » |
Quote Modify
|
Here is another idea. Given 2 (input) bits predicting a suit for 2 cards,
we predict the suit of at least one card, take 2 (output) bits from the backs of the two cards, and either gain a bit (which card's suit was predicted), or have an extra correct prediction. The oportunities for lies also exist: a lie can encode an extra bit in the color of the mispredicted suit.
Unfortunately, all my attempts at mixing and matching the schemes and lies result in no more than 24 guaranteed guesses and wasted bits here and there.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove