wu :: forums « wu :: forums - Guessing Cards Suit » Welcome, Guest. Please Login or Register. Dec 16th, 2018, 9:55pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: ThudnBlunder, Grimbal, Eigenray, Icarus, SMQ, william wu, towr)    Guessing Cards Suit « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 Author Topic: Guessing Cards Suit  (Read 9737 times)
Leo Broukhis
Senior Riddler

Gender:
Posts: 459
 Re: Guessing Cards Suit   « Reply #25 on: Apr 30th, 2004, 7:58pm » Quote Modify

Here is how to predict at least 5 out of the last 6 cards given one input bit i:

(suits of cards are referred to as A to F, orientations - as a to f)

(i,a) predicts A and/or B.

If A != B, then (predicted(B), c) predicts C

(b, d) predicts D

e predicts E
F is known
 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7433
 Re: Guessing Cards Suit   « Reply #26 on: May 1st, 2004, 10:15am » Quote Modify

Thanks, Leonid!  I know now how to guarantee 24 predictions.

Shortly:
provided one bit of information from previous cards, you can guess 2 cards in a group of 3 and provide one bit of information out.
 IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2818
 Re: Guessing Cards Suit   « Reply #27 on: May 1st, 2004, 2:53pm » Quote Modify

I can find a naive implementation which guarantees (given an input bit to a group of 3) either 2 right and an output bit, or all 3 right and no output - in the case where the first two cards have the same suit - in which case you can't tell which of the first two is being accurately described, so can't create a bit that way. Of course, if you wished, you could choose to sacrifice the third card in order to pass two bits (second and third card orientations) but I can't believe that's optimal...

Oh, and the problem statement still bugs me - I keep reading it as asking for maximizing the number of predictions where the magician knows before turning the card which suit it actually is - while using current methods, a number of correct predictions are uncertain in advance. The minimal rewording to remove this niggle would be to move "guaranteed" to before number. The one I'd prefer would be "maximize the number of correct predictions in the worst case"
 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7433
 Re: Guessing Cards Suit   « Reply #28 on: May 1st, 2004, 5:00pm » Quote Modify

You are right.  I assumed that the magician is told after his prediction if it was true or not.  This gives him back one bit of information.  And for number of predictions, 24 would be the guaranteed minimum of correct predictions.
 IP Logged
fieldazed
Junior Member

Gender:
Posts: 55
 Re: Guessing Cards Suit   « Reply #29 on: Dec 2nd, 2012, 6:38am » Quote Modify

This is a very cool puzzle.  Have been working on a similar problem on a different site and have a solution for 26 correctly predicted out of 36 if anyone has any interest in reviving this topic.
 IP Logged
fieldazed
Junior Member

Gender:
Posts: 55
 Re: Guessing Cards Suit   « Reply #30 on: Dec 4th, 2012, 11:36am » Quote Modify

hidden below is a solution that guarantees at least 25 of 36 to get the juices flowing if anyone chooses.  think it's still quite challenging to go from 25 to 26.  at least is was for me.  anyway, fwiw -

The orientation of the first and second cards gives the suit to respond to both cards 2 and 3.  Will address the case if both are the same suit later but if cards 2 and 3 are different suits, the assistant could choose either to be correctly predicted giving the magician an extra "bit" of information.  The orientation of card 3 then acts as the first card and this process can be repeated.  So cards x(2,3) (4,5) (6,7) (8,9) (10,11) (12,13) could give 6 correct suit predictions and 7 extra bits (the seventh being the orientation of card 13).  Using five of these bits along with the orientation of the next five cards defines the suits of those next five cards.  Incorrectly indicating any one or none of those five can be achieved sixteen or 2^4 different ways - five extra bits spent and four bits returned with four of five suits predicted.  Repeating this two more times gives a total of 18 out of 28 suits correct with four extra bits yielding 22 of 32 correct.  The orientation of cards 33 and 34 defines the suit of card 34 and the last two suits can both be predicted as earlier described in this thread.

If one of pairs (2,3) (4,5) (6,7) (8,9) (10,11) (12,13) were the same suit, 7 of 13 would be predicted correctly with only six extra bits.  The orientation of card (14) gives a seventh extra bit.  Continuing from here as above yields 23 out of 33 suits predicted correctly and the last two cards predicted as before.  This method or similar can be extended to examples where two or more of the initial six pairs are the same suit.
 IP Logged
jollytall
Senior Riddler

Gender:
Posts: 573
 Re: Guessing Cards Suit   « Reply #31 on: Dec 30th, 2012, 2:18am » Quote Modify

It will be a bit long, sorry:

First comment:
In the convicts guessing hats problem (100 stood in a row, everybody can see all those in front of them and can loudly guess his hat's colour being B or W) the best solution is if every guess includes all the information that can be collected seen (in front of him) and heard (behind him). This would give a hint here that also the best strategy MIGHT need to use extra information of the future (the assistant can flip through all the cards in advance) and the success of past guessings.

Second comment:
A nice solution to give 3 out of 5 in any case is as follows:
Guess Black for the first one and decide C/S based on the direction. If indeed B, then we have one hit and need to guess right 2 from 4 (easy).
If the first is Red, then the direction does not refer to this card, but the next three, giving whether B or R are more (in the THREE ahead!). Knowing that, we can guess 2nd to 4th all for this colour, the direction giving the split between C/S or D/H. If all three are right then we have the 3/5. If one was wrong (2 are always right), then that can give an extra bit, what we use for the 5th card, i.e. still has 3 out of 5.
This gives us 21/35, and the last one is always given, so it gives 22.
This is far from ideal, but again shows that a logic MIGHT use information running ahead.

Third comment:
All the posts so-far use only the Suit of the cards. I am not sure how to use, but there is much more information available. All the turned up cards has also a value. Using the first x card, there are surely patterns that can be idetified. Then one bit of information can say, whether to use it or not, or few bits can be used to identify a logic, how to use this pattern and it can give a lot of vaulable information for the remaining cards. This almost surely improves significantly the expected value of the right guesses, but I do not see, if at all, it can also improve the worst case value. Nonetheless, we should not exclude this option either.

Having said all these, I have a solution that uses much less information, but still gives a solution to guess right at least 27.

See next post for the details.
 IP Logged
jollytall
Senior Riddler

Gender:
Posts: 573
 Re: Guessing Cards Suit   « Reply #32 on: Dec 30th, 2012, 2:18am » Quote Modify

The basics of the logic:
Every time the Magician is left with n cards, he knows exactly the distribution of C+D+H+S=n. He also might or might not have a Carry Over Bit from the previous step(s).
Here I do one restriction already. I do not allow to use more than 1 COB. There might be better strategies, where e.g. the deck is split into blocks and every block leaves a COB, while at the end we use all those COBs collected. In my modell I do not allow that.

Based on the information the Magician has, he can have three basic strategies:

Strategy A
Say a given Suit, regardless whether he has COB or not and what way the card stands. Theoretically this strategy would even allow to carry over 2 bits, one brought from earlier and one from this card. Still, as said above, in this case I only carry over one bit.
He is either right or wrong, but surely carries over 1 COB.

Strategy B
Try to use only 1 bit of information, either because there is no COB brough from earlier, or simply because he does not want to use it, does not need it.
Here the Assistant has almost unlimited potential strategies. As shown above, the Assistant might decide what the meaning of that bit that is going to be used, based on millions of options, using all the information he has about the deck. Nonetheless, I make again a great simplification. He can only assign 1 or 0 based on the suit of the CURRENT (next to be guessed) card.It still gives him 16 potential strategies (what to show for every C,D,H,S). My modell has to choose the best out of these 16 strategies (and of course both the Assistant and the Magician must remember for every C+D+H+S left - but this is why they are magicians).
But the goodness of the Assistant assignment also depends on what the Magician says when he is using this one bit of information. Again, he has 16 options (4 suits to choose from if he got a 1, times, 4 suits to choose from if he got a 0).
Depending on the Assistant strategy and the Magician strategy there are still two potential outcomes. He guessed right or he did not (if not then there are 3 potential wrong outcomes).
If he guessed right then I consider the 1 bit he had used, is used up completely. He might have had a second bit not used, so he can have a COB still for the next step.
If he guessed wrong then this information was not for this card (see the second comment in my previous post, what happens with the 1st from the 5 if it is Red), so it can be carried over. Theoretically again, he could carry over THIS bit and also the SECOND bit not used (if he had one). As said twice above, I do not allow this, he carries on maximum ONE bit. By the way it seem logic also to do this. If he had 2 bits available then he should not make a mistake. If one bit is not enough to make sure, use the second too. So, it is not a real restriction I think, but again, theoretically there might be a better solution.

Strategy C
He uses 2 bits of information. This Strategy is only available if he has got a COB from earlier and also uses the bit from the current card. Here I assume he uses completely BOTH bits and therefore guesses this card surely, but looses the chance to have a COB carried forward.
This again seems to be logic, but in reality it is a restriction again. There could have been a mixed strategy, what I exclude. E.g. there are three kind of suits left in the deck only, C,D,H. If the first bit is 0 then it is Black and therefore C and the second bit does not need to be used, can be carried over. If it is 1, then it is Red, so we need the second bit as well to decide D/H. In my model, I do not allow this: if he decides to use 2 bits, then both are gone in this step, no COB.
It is theoretically a restriction, but I think in reality not really. Either it can occur as above if there are three suits left only, what is already a simplified case, i.e. not likely that the loss of this bit will change the worst case scenario. Alternatively, a mixed strategy could also be used, e.g. if there are still 4 suits but very uneven distribution (CDHs). In this case it might be a good logic to use the first bit for B/R. If B then do not use the second bit, but guess C (C>>s) and let a small chance for guessing wrong, in which case the remaining distribution is even more unequal, thus easier.

With smartly using a combination of only these three strategies I can get to my result.

See next post.
 IP Logged
jollytall
Senior Riddler

Gender:
Posts: 573
 Re: Guessing Cards Suit   « Reply #33 on: Dec 30th, 2012, 2:19am » Quote Modify

I do the whole thing rolling backwards:

n=1

The 36th card is given in any case (what is left). With a naming convention CDHSb (where C is the number of Clubs left, etc. and "b" is either TRUE or FALSE showing whether there is a COB available), we can say that 1000T, 1000F, 0100T, etc. are all giving 1 guaranteed cards using StrategyA above (say the Suit regardless of any information).
In the future description the symmetrical permutations are leave out (1000T=0010T).

***

n=2

If the 35-36th are the same then again (2000T or 2000F), they are given using StrategyA. If they are different (1100T or 1100F), then the 35th can indicate which of the 2 is it (Strategy B, using only one bit, no need to use the COB).

***

n=3

If the 34-36th are the same, then solved (3000T or 3000F, Strategy A).
If they are 2100T or 2100F, then the 34th should indicate whether it is the rare or not (Strategy B, 1 guaranteed guess and leads to 1100T/1100F or 2000T/2000F). Anyway, they are again solved.
The only problem is if the last 3 are all different (1110). 1110F cannot be solved without carried over bit (use Strategy A, guess something and will be 1100T), giving in total only 2 good guesses. With a COB 1110T it can be solved with Strategy C giving one good guess and leading to 1100F.

***

n=4

The 33-36th has even more options:
4000b leads to 3000b using Strategy A.
3100b. The 33rd should tell whether rare or not, using Strategy B, leading to 3000b or 2100b.
2200b. The 33rd should tell which is it (Strategy B, leading to 2100b).

It really gets interesting here.

2110F. If there is no COB, we have 3 potential suits in position 33 and only one bit of information. Surely cannot be done with 100% accuracy, i.e. cannot guess all the 4 right. To have 3 right is pretty easy.

2110T. Using a mixed strategy all the 4 can be guessed right.
Let's use the COB to tell whether it was a rare (D or H) or it was one of the two C-s.
If C then we say so (right guess) and use the card information as a COB for the last ones (1110T - 3 good guesses guaranteed), i.e. altogether 4 good guesses done.
If not C then we use the second available bit too, and guess D or H right, leaving us with 2100F, again 3 more good guesses guaranteed.
So, with a mixed strategy 2110T=4. Nonetheless, as I said in my posts above I do not allow mixed strategy, and thereore my 2110T=3 only.

1111F. If we have no carry over bit, then the 33rd is a guess (Strategy A) but gives a COB, so the last three can be solved (1110T).
1111T. Even if we have a COB, then it can be good to fix the 33rd (Strategy C giving 1110F=2).
So both 1111F=3 and 1111T=3.

***

n>4
The number of options grows on, so I used a program to work out the best logic, using all the above information (no mixed strategy). This gives the 27 maximum. The below table shows the most available for various n-s (always the worst combination. I have all the combination in details, if you are interested).
It would make sense, to build in the mixed strategy as well, to see if it can further increase the number.

Best available for TotalNumber=1 is 1
Best available for TotalNumber=2 is 2
Best available for TotalNumber=3 is 2
Best available for TotalNumber=4 is 3
Best available for TotalNumber=5 is 4
Best available for TotalNumber=6 is 4
Best available for TotalNumber=7 is 5
Best available for TotalNumber=8 is 6
Best available for TotalNumber=9 is 6
Best available for TotalNumber=10 is 7
Best available for TotalNumber=11 is 8
Best available for TotalNumber=12 is 8
Best available for TotalNumber=13 is 9
Best available for TotalNumber=14 is 10
Best available for TotalNumber=15 is 10
Best available for TotalNumber=16 is 11
Best available for TotalNumber=17 is 12
Best available for TotalNumber=18 is 12
Best available for TotalNumber=19 is 13
Best available for TotalNumber=20 is 14
Best available for TotalNumber=21 is 14
Best available for TotalNumber=22 is 15
Best available for TotalNumber=23 is 16
Best available for TotalNumber=24 is 16
Best available for TotalNumber=25 is 17
Best available for TotalNumber=26 is 18
Best available for TotalNumber=27 is 18
Best available for TotalNumber=28 is 19
Best available for TotalNumber=29 is 20
Best available for TotalNumber=30 is 21
Best available for TotalNumber=31 is 22
Best available for TotalNumber=32 is 23
Best available for TotalNumber=33 is 24
Best available for TotalNumber=34 is 25
Best available for TotalNumber=35 is 26
Best available for TotalNumber=36 is 27
 IP Logged
fieldazed
Junior Member

Gender:
Posts: 55
 Re: Guessing Cards Suit   « Reply #34 on: Jan 1st, 2013, 9:32am » Quote Modify

hello there jollytall - great to now know of your interest in this puzzle.  your solution is quite good.  think tho there may be a glitch in your program and your method correctly guarantees a minimum of 24 out of 36 cards.
 IP Logged
jollytall
Senior Riddler

Gender:
Posts: 573
 Re: Guessing Cards Suit   « Reply #35 on: Jan 3rd, 2013, 7:58am » Quote Modify

Can easily be. It would be good if someone else (you, maybe) could reproduce it and see which is the first number where our results differ.
I will also make a double-check.
 IP Logged
fieldazed
Junior Member

Gender:
Posts: 55
 Re: Guessing Cards Suit   « Reply #36 on: Jan 3rd, 2013, 8:48am » Quote Modify

Did not run a program.  Made my previous statement based on studying your method as well as seeing the pattern in your results break at TotalNumber = 30 without any logic that i can discern as to why.
 IP Logged
jollytall
Senior Riddler

Gender:
Posts: 573
 Re: Guessing Cards Suit   « Reply #37 on: Jan 3rd, 2013, 9:00am » Quote Modify

This is worse than that
There was a typo in the program. Now the best is only 19...
Need to implement the mixed strategy in it. That might improve back again closer to your 26.
 IP Logged
fieldazed
Junior Member

Gender:
Posts: 55
 Re: Guessing Cards Suit   « Reply #38 on: Jan 7th, 2013, 11:33am » Quote Modify

here's a hint as to a strategy that at least i needed to guarantee a minimum of 26 out of 36 correctly predicted suits:

if you can find two different yet distinguishable paths, depending on which is indicated by the assistant gives another bit of info.
 « Last Edit: Jan 8th, 2013, 5:47am by fieldazed » IP Logged
jollytall
Senior Riddler

Gender:
Posts: 573
 Re: Guessing Cards Suit   « Reply #39 on: Jan 10th, 2013, 11:52am » Quote Modify

I tried the simple mixed strategy, i.e. if we have a COB available then either we use it or we don't depending on how many different suits are still there.
If 4 then we use it always and guess right.
If 3 then we use one bit for the most likely one (or one of them if there are 2 or 3 equally likely ones) and 2 bits for the other 2 less frequent.
If 2 or 1 different suits are left, then we do not use this method at all, one bit is enough to guess right the card and can carry on the COB brought.

Unfortunately it did not change my 19.

Conclusion: That is surely not good if you use your available bit for solving the upcoming cards. As said above by Leo, it is sometimes a better strategy if one is intentionally missed in order to convey messages with it.
 « Last Edit: Jan 10th, 2013, 12:50pm by jollytall » IP Logged
 Pages: 1 2 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »