Puzzle: optimal guessing in a card game

You and a friend play a guessing game with cards.

The deck consists of four black cards and four red cards. The game is played as followed.

You announce a guess of a card, and then your friend flips over the card on the table to see if you are correct. The game continues card by card until the deck is finished.

You get $1 for each card that you guess correctly.

Questions:

1. Imagine you use a coin flip to determine your guesses (if heads you guess black, if tails you guess red). How much money do you expect to win?

2. Can you figure out a better guessing strategy?

3. How much money do you expect to win with an optimal guessing strategy?

Feel free to leave a comment with how long you took or the method you used to solve the puzzle.



Share this post:

| More

Previous post:

Next post:



  • RasmusF

    1) 8*.5*$1 = $4

    2) Always guess the color with the most cards remaining in the deck. It’s pretty easy to see why when considering the case of one card left in the deck.

    3) I couldn’t come up with a quick solution for calculating the value of the strategy, so I didn’t bother.

    It took a few seconds to come up with this strategy.

  • Scott

    1) The probability of getting a card correct is independent of any previous guesses, and it 50% for each card. You have an expected winning of $0.50 for each card * 8 cards = $4.

    2) At this point, I think guessing whichever color has the most cards remaining is a good strategy, using a coin flip for ties.

    3) I identified 14 possible paths this can take, when you reduce each point in time to the ratio of one color to the other:

    Ratios for:
    1st Card 2nd Card 3rd Card 4th Card 5th Card 6th Card 7th Card 8th Card
    Case 1: 4 to 4 4 to 3 4 to 2 4 to 1 4 to 0 3 to 0 2 to 0 1 to 0
    Case 2: 4 to 4 4 to 3 4 to 2 4 to 1 3 to 1 3 to 0 2 to 0 1 to 0
    Case 3: 4 to 4 4 to 3 4 to 2 4 to 1 3 to 1 2 to 1 2 to 0 1 to 0
    Case 4: 4 to 4 4 to 3 4 to 2 4 to 1 3 to 1 2 to 1 1 to 1 1 to 0
    Case 5: 4 to 4 4 to 3 4 to 2 3 to 2 3 to 1 3 to 0 2 to 0 1 to 0
    Case 6: 4 to 4 4 to 3 4 to 2 3 to 2 3 to 1 2 to 1 2 to 0 1 to 0
    Case 7: 4 to 4 4 to 3 4 to 2 3 to 2 3 to 1 2 to 1 1 to 1 1 to 0
    Case 8: 4 to 4 4 to 3 4 to 2 3 to 2 2 to 2 2 to 1 2 to 0 1 to 0
    Case 9: 4 to 4 4 to 3 4 to 2 3 to 2 2 to 2 2 to 1 1 to 1 1 to 0
    Case 10: 4 to 4 4 to 3 3 to 3 3 to 2 3 to 1 3 to 0 2 to 0 1 to 0
    Case 11: 4 to 4 4 to 3 3 to 3 3 to 2 3 to 1 2 to 1 2 to 0 1 to 0
    Case 12: 4 to 4 4 to 3 3 to 3 3 to 2 3 to 1 2 to 1 1 to 0 1 to 0
    Case 13: 4 to 4 4 to 3 3 to 3 3 to 2 2 to 2 2 to 1 2 to 0 1 to 0
    Case 14: 4 to 4 4 to 3 3 to 3 3 to 2 2 to 2 2 to 1 1 to 1 1 to 0

    I apologize if the above does not view well. The chance of winning each, then, is equal to the larger of the ratio to the total (that is, for 4 to 3, the chance of winning is 4/7). Since you stand to win $1 for each correct guess, your winnings for each guess are equal to the percentage chance of guessing correctly. I’ve provided the total winnings for each case, with the average winnings over all cases, since each is as likely as the other:

    1st Card 2nd Card 3rd Card 4th Card 5th Card 6th Card 7th Card 8th Card Total
    Case 1: 50% 57% 67% 80% 100% 100% 100% 100% $6.54
    Case 2: 50% 57% 67% 80% 75% 100% 100% 100% $6.29
    Case 3: 50% 57% 67% 80% 75% 67% 100% 100% $5.95
    Case 4: 50% 57% 67% 80% 75% 67% 50% 100% $5.45
    Case 5: 50% 57% 67% 60% 75% 100% 100% 100% $6.09
    Case 6: 50% 57% 67% 60% 75% 67% 100% 100% $5.75
    Case 7: 50% 57% 67% 60% 75% 67% 50% 100% $5.25
    Case 8: 50% 57% 67% 60% 50% 67% 100% 100% $5.50
    Case 9: 50% 57% 67% 60% 50% 67% 50% 100% $5.00
    Case 10: 50% 57% 50% 60% 75% 100% 100% 100% $5.92
    Case 11: 50% 57% 50% 60% 75% 67% 100% 100% $5.59
    Case 12: 50% 57% 50% 60% 75% 67% 100% 100% $5.59
    Case 13: 50% 57% 50% 60% 50% 67% 100% 100% $5.34
    Case 14: 50% 57% 50% 60% 50% 67% 50% 100% $4.84
    Average: $5.65

  • Eyal

    Assuming the cards are randomly shuffled, Scott’s case 1 is less likely than the other cases. The only way for his case 1 is RRRRBBBB or BBBBRRRR. The number of ways to permute the red and black cards is 8!/4!/4!, or 70. Case 1 has only 2 ways, so it must be 2/70 or 1 in 35. 14 doesn’t divide 35 so by the pigeonhole principle, that solution can’t be correct.

    Also, who’s to say that the cards are shuffled fairly? Maybe they are sorted specifically to mess up your strategy? That’s a harder expectation to compute!

  • Eyal

    For example, say that you’re down to the last three cards, RRB. If the cards are random, you’ll guess red and your expectation for all three possibilities are:

    RRB: 1+0.5+1 = 2.5
    RBR: 1+0.5+1 = 2.5
    BRR: 0+1+1 = 2

    So you win 7/3 on average. But your opponent, he’s no dummy. He’s knows that you’re going to guess Red, so he always puts Black. But you know he knows. But he knows you know he knows… etc. So you end up with a pay matrix like this:

    3,1.5
    2,2.5

    Left column, next card is black, right column, next card is red. Top row, you guess black, bottom row, you guess red.

    The Nash equilibria are 50-50 for next card but 75-25 in favor of guessing Red! The expectation comes to 9/4, a little less money than 7/3 of random.

    You must 9/4 into the matrix for 4 cards and work your way up to the answer for 8 cards. By this point, maybe best to use a computer to get the answer!

  • Eyal

    I wrote code to compute it:

    http://pastebin.com/MryKC2Bj

    If your friend just shuffles the cards randomly then your expectation is: 373/70 ($5.32857) but if your opponent is smart, it’s 163/32 ($5.09375).

    The math for the expectation is complex but lots of variables cancel out.

  • Scott

    @Eyal:

    Yes, my cases should not be weighted equally, this was an assumption on my part. I had not considered that there could be different numbers of combinations resulting for each case. Thanks for pointing this out!

  • William

    @Eyal:

    I don’t think this is a 2-player game. I think the deck is in a predefined random order, and that the friend is just there to flip the next card over, and presumably pay you.

  • http://www.mindyourdecisions.com/blog/ Presh Talwalkar

    Thanks all for the responses. Here are the answers.

    1. Imagine you use a coin flip to determine your guesses (if heads you guess black, if tails you guess red). How much money do you expect to win?

    You would expect to guess half of the cards by pure chance, and so that means you would expect to win $4.

    2. Can you figure out a better guessing strategy?

    Of course you can do better because you see the cards one by one as they are flipped up.

    We use backwards induction to find the result. Clearly you can guess the last card correctly if you have been keeping track. But what about the second to last card? You know there are two cards remaining, so your guess should be based on the color of those cards. The guessing strategy is this: guess the color that has the most cards remaining in the deck.

    We can keep reasoning backwards to find this is the best strategy for the entire game. (If there is an equal number, then flip a coin and pick either)

    3. How much money do you expect to win with an optimal guessing strategy?

    The answer is 373/70, or about 5.3, as Eyal said above.

    The solution depends on using a random walk interpretation to the game. There is a nice step-by-step exercise in the following free textbook on page 251 and 252, exercises 25 and 26:

    Intro to probability

    If you are really into the math, then you can find the original derivation from Persi Diaconis and Ronald Graham in a 1981 paper:

    The analysis of sequential experiments with feedback to subjects

    (I admit this paper was above my head–but I’m sure someone out there will understand and appreciate it)

    Bonus: deck is not fairly shuffled

    Eyal raised a great point that the deck may not be fairly shuffled, making the optimal guessing strategy suffer.

    I have not had time to solve this problem, so for now I will take Eyal’s word on the answer!

  • Pingback: 3 ways sleeping can help you get rich and save money - Mind Your Decisions

  • Anand Gautam

    Hi Presh,

    First of all, really love your blogs and puzzles. I follow it as religiously as facebook and faking news :)
    Usually late in reading/solving, so this is my first comment.

    Logic of the solution was fairly obvious. Didn’t know how to solve it efficiently, so I opened an excel and solved it by brute force. Took me 15 minutes.

    In the optimal strategy, following are the expected earnings step wise: 0.5 + 0.57 + 0.57 + 0.63 + 0.63 + 0.71 +0.71 + 1.0 = 5.33

    Its a simple excel, but not sure how can I share it. Was happy to see the answer matching, hence posting :)

    Regards,
    Anand.

  • anon

    Hello,

    I got a different answer: 5.3777. Would someone kindly point out the flaw in my solution, if any?

    1st card: 1/2
    2nd: 4/7

    For the 3rd card, the possibilities for the remaining cards are 3 Red, 3 Black (1/2 chance), or 2R4B (1/4 chance), or 4R2B (1/4 chance).

    This gives expected winnings of (1/2)*(3/6) + (1/4+1/4)*(4/6), or 7/12.

    Reasoning similarly, the chances of getting 1R4B, 2R3B, 3R2B, 4R1B when there are 5 cards remaining is in the ratio 1:3:3:1, so that the expected winnings for the 4th card is 13/20.

    5th card: Ratio 1:4:6:4:1, winnings 11/16
    6th: Ratio 3:5:5:3, winnings 19/24
    7th: Ratio 11:10:11, winnings 19/32
    8th: winnings 1

    This gives me a total of 5.3777, as previously mentioned.

    Any ideas?

  • Anand Gautam

    “For the 3rd card, the possibilities for the remaining cards are 3 Red, 3 Black (1/2 chance), or 2R4B (1/4 chance), or 4R2B (1/4 chance).”
    The probabilities in bracket are incorrect. The 3B3R scenario will occur with a 4/7 probability and 2B4R or 4B2R will occur with a 3/7 probability.

  • anon

    Ouch, I see my error. Thanks.

Previous post:

Next post:

This site is for recreational and educational purposes only (privacy policy)

Powered by WordPress