Card guessing game

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

aleph_one
Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

Card guessing game

Postby aleph_one » Thu Dec 02, 2010 12:04 am UTC

(Stolen from this MathOverflow answer by Kevin Buzzard. Don't look at the comment after it; it has the key tio the solution.)

A friend deals cards face-up one a time from a shuffled deck of 26 red cards and 26 black cards. At some point before all the cards are dealt, you must call "stop", after which you win if the next card dealt is red. What is the optimal winning probability?

User avatar
imatrendytotebag
Posts: 152
Joined: Thu Nov 29, 2007 1:16 am UTC

Re: Card guessing game

Postby imatrendytotebag » Thu Dec 02, 2010 1:11 am UTC

A naive approach:

Spoiler:
Let P(R,B) be the probability of winning with an optimal strategy, given R red cards and B black cards remaining.

Supposing there are R reds and B blacks, one strategy is to say "stop", which has probability R/(R + B) of winning.

If you don't say stop, you have R/(R+B) of uncovering R and B/(R+B) of uncovering a B. This gives a probability [imath]\frac{R}{R+B}P(R-1,B) + \frac{B}{R+B}P(R,B-1)[/imath]. We can now show by induction (on R + B) that P(R,B) = R/(R + B).

Proof: The base case is R + B = 1. In this case we only have 1 red card or 1 black card, and either way the probability of winning is clearly R/(R + B).

By induction, suppose the theorem holds for R + B = k - 1, and let R + B = k. Then, with R reds and B blacks there are tw choices. The first choice gives R/(R+B). The second choice gives [imath]\frac{R}{R+B}\cdot{R-1}{R + B - 1}+ \frac{B}{R+B}\cdot\frac{R}{R + B - 1} = \frac{R}{R+ B}[/imath], by induction, which we can use since (R - 1) + B = R + (B - 1) = k - 1. This shows either strategy gives R/(R+B).

This means an optimal strategy is just to say "stop" immediately. An equally valid strategy is to say "stop" after any, predetermined, number of cards are revealed.
Hey baby, I'm proving love at nth sight by induction and you're my base case.

jbwraith
Posts: 13
Joined: Tue Dec 21, 2010 4:01 am UTC

Re: Card guessing game

Postby jbwraith » Thu Dec 23, 2010 1:11 am UTC

Better one: count black cards until you have counted 26. Then say stop. If you get to a high enough number of black cards, then you can take a guess at it as well, but 26 blacks guarantees that the next card will be red.

aleph_one
Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

Re: Card guessing game

Postby aleph_one » Thu Dec 23, 2010 1:21 am UTC

jbwraith, the strategy of guessing only guess after seeing 26 black will fail if the last card is black, since you'll have to guess before it. In fact, it only works half the time, exactly if the last card is red. You suggested simply guessing after you get a large number of black cards - can you refine that into a precise strategy?

User avatar
phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Card guessing game

Postby phlip » Thu Dec 23, 2010 1:42 am UTC

Thinking aloud:
Spoiler:
Maybe this puzzle is like this one, where you also need to act probabilistically in order to improve your odds? I think that the best any deterministic strategy will get is 50/50 (trendytotebag showed that quite well), increases in the chance of you winning if you say "stop" being balanced by the chance you never say "stop" at all... [edit] Actually, reading it again, it looks like trendy's post is that every deterministic strategy where you always say "stop" at some point is 50/50... and any strategy where you might not say "stop" cannot be made worse by saying "stop" on the last card - if it's red, you go from losing to winning, and if it's black then nothing changes. [/edit]

What are your odds of winning if, say, at each opportunity, you say "stop" with probability equal to [an increasing function of] the proportion of the remaining cards that are red? So 50% chance you'll say "stop" immediately... if the first card is red you'll then say "stop" 25/51 of the time, but if the first card is black you'll then say "stop" 26/51 of the time, etc. Sounds like it would be kinda painful to analyse by hand, but I'll run some calculations, see if it does better than 50/50...

[edit] Looks like that's also 1/2. In fact, I think trendy's proof can be adapted to non-deterministic strategies too... at each stage, if you call "stop" you have a R/(R+B) chance of winning, and if you don't call stop, then by the inductive hypothesis, you have a R/(R+B) chance of winning... so regardless of your strategy's method of choosing whether to say "stop", be it fixed or non-deterministic, you have a R/(R+B) chance of winning at this step, which completes the induction... [/edit]

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

jbwraith
Posts: 13
Joined: Tue Dec 21, 2010 4:01 am UTC

Re: Card guessing game

Postby jbwraith » Sun Dec 26, 2010 6:11 pm UTC

aleph_one wrote:jbwraith, the strategy of guessing only guess after seeing 26 black will fail if the last card is black, since you'll have to guess before it. In fact, it only works half the time, exactly if the last card is red. You suggested simply guessing after you get a large number of black cards - can you refine that into a precise strategy?


This is true.

Disclaimer- I am not as good at writing things out mathematically as other people on the forum, so please bear with me on this.

There are 26 red and 26 black cards. We can modify a blackjack card-counting technique to help count whether you should say stop or not.

Start your count at 0. Any time a black card comes up, add 1. Any time a red card comes up, subtract 1. The higher your count, the better your odds of winning. If you get to a +5 or higher, you should say stop because there are 5 less black cards than red in the deck. Measuring probability of you winning at a full deck, 3/4 deck, half deck, and 1/4 deck:

Full deck- 50% chance of winning

3/4 deck- 56% chance of winning

1/2 deck- 69% chance of winning

1/4 deck- 69% chance of winning.

You can vary the number your count to, but if you wait until a count of +5 and have gone halfway through the deck, you have a better than 2/3 chance of winning.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Card guessing game

Postby Qaanol » Sun Dec 26, 2010 9:42 pm UTC

The reason that works in Blackjack is that you can vary the size of your bets from hand to hand (or do what they did in Bringing Down the House and have multiple people involved, betting different amounts) without the whole deck being reshuffled each hand. In this game there is only one bet, and you have to make it before the start of the game, when the deck is full. Your odds of winning are determined by what you know at the time you made the bet.
wee free kings

Moose Hole
Posts: 398
Joined: Fri Jul 09, 2010 1:34 pm UTC

Re: Card guessing game

Postby Moose Hole » Mon Dec 27, 2010 3:29 pm UTC

Yeah, you have a 69% chance at half deck, IF you are at +5, but that won't always happen, and you could be at 0 or negative the entire game. The thing is, if there are still two colors in the deck, then it doesn't matter when you say stop, because the next card could still be black. In fact, if there is only one color remaining, it still doesn't matter when you say stop. I'm pretty sure this game has an average of 50% chance of winning regardless of when stop is said.

jjfortherear
Posts: 103
Joined: Wed Oct 27, 2010 12:44 am UTC

Re: Card guessing game

Postby jjfortherear » Thu Dec 30, 2010 4:26 am UTC

My friend and I just spent 3-4 hours doing this experimentally, and I'd really like to see some maths.

Lets say you're dealing from the top of the deck, and whenever stop is called, you always pick the bottom card. This card HAS to be 50/50, right? Well, why should it matter what card is picked, in that case? Lets say you have 10 cards, 5 and 5, and 4 reds are dealt. This means that while the bottom one (or any other one) has to be 50/50, there's only 1 red card and 5 blacks. How does this square?
Qaanol wrote:Actually this could be a great idea. See, you just have to bill the mission to an extrasolar planet as a mission, and then let all the fundamentalists from all religions be the missionaries.

User avatar
Krawl
Posts: 14
Joined: Thu Dec 30, 2010 5:29 am UTC
Location: East of West Edmonton Mall and West of the Far East.
Contact:

Re: Card guessing game

Postby Krawl » Thu Dec 30, 2010 6:29 am UTC

Okay, here's my best bet at winning.

Spoiler:
Count the cards. You can count two things at once, yes? In your head, keep track of how many black are placed down, and how many red are placed down. If you're lucky, you'll start to see a rapid increase in your chance of getting a red card near the end, and if that fails and you reach 25 red before the black cards reach a high number, you're better of throwing your stop in at any random point. But the chances are that it won't happen that way.
Warning! Sex Facts:
Spoiler:
A single sperm has 37.5MB of DNA information in it. That means that a normal ejaculation represents a date transfer of 1587.5TB.
That's a lot of Fucking Data! Haha! Get it? Fucking.

Image

redrogue
Posts: 116
Joined: Tue Dec 15, 2009 9:17 pm UTC

Re: Card guessing game

Postby redrogue » Thu Dec 30, 2010 9:18 pm UTC

jjfortherear wrote:This means that while the bottom one (or any other one) has to be 50/50, there's only 1 red card and 5 blacks. How does this square?


Because the deck order stays put once it's been randomized. If you shuffled the remaining cards each time, the odds would change to reflect the number of black and red cards remaining.

I don't know if I'll be able to explain this one. It's a lot like the Monte Hall problem, and how your odds of winning the car stay at 1/3 when Monte reveals the goat behind door #2... rather than evening out 50/50.
Is 'no' your answer to this question?

jjfortherear
Posts: 103
Joined: Wed Oct 27, 2010 12:44 am UTC

Re: Card guessing game

Postby jjfortherear » Thu Dec 30, 2010 9:49 pm UTC

redrogue wrote:
jjfortherear wrote:This means that while the bottom one (or any other one) has to be 50/50, there's only 1 red card and 5 blacks. How does this square?


Because the deck order stays put once it's been randomized. If you shuffled the remaining cards each time, the odds would change to reflect the number of black and red cards remaining.

I don't know if I'll be able to explain this one. It's a lot like the Monte Hall problem, and how your odds of winning the car stay at 1/3 when Monte reveals the goat behind door #2... rather than evening out 50/50.


Your odds actually go up to 2/3, as long as you switch, don't they? The only time you wouldn't win by switching is if you initially picked the car, which only happens 1/3, so you get 2/3 by switching.
Qaanol wrote:Actually this could be a great idea. See, you just have to bill the mission to an extrasolar planet as a mission, and then let all the fundamentalists from all religions be the missionaries.

redrogue
Posts: 116
Joined: Tue Dec 15, 2009 9:17 pm UTC

Re: Card guessing game

Postby redrogue » Thu Dec 30, 2010 10:41 pm UTC

Right. If you switch doors, you'll win it 2/3 of the time.

I was trying to illustrate that the odds of the bottom card in a shuffled deck should stay 50/50 even if you reveal more cards. In the Monte Hall problem, if you keep your initial door choice, your odds of winning STAY at 1/3 after one of the other doors is opened.
Is 'no' your answer to this question?

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Card guessing game

Postby jestingrabbit » Fri Dec 31, 2010 3:57 am UTC

redrogue wrote:Right. If you switch doors, you'll win it 2/3 of the time.

I was trying to illustrate that the odds of the bottom card in a shuffled deck should stay 50/50 even if you reveal more cards. In the Monte Hall problem, if you keep your initial door choice, your odds of winning STAY at 1/3 after one of the other doors is opened.


What you're trying to show isn't right though. If there are 51 cards revealed, then the last card is known too. Each card revealed gives you information about that final card, in that they tell you what it is not.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jjfortherear
Posts: 103
Joined: Wed Oct 27, 2010 12:44 am UTC

Re: Card guessing game

Postby jjfortherear » Fri Dec 31, 2010 6:20 am UTC

so, what my friend and I were doing as dealing out of a deck of n red and black cards, until n-1 of either suit was out. then, tallying how many times the next card was of the same suit, and it ended up being about 1/3 of the time - though this is likely due to the fact that most of the time, there ended up being 3 cards left (one of which is the same suit, so 1/3 gg). My question is, had we been taking the back card every time, it should've been 50 percent, right? and if that's true, why not any card?
Qaanol wrote:Actually this could be a great idea. See, you just have to bill the mission to an extrasolar planet as a mission, and then let all the fundamentalists from all religions be the missionaries.

User avatar
mmmcannibalism
Posts: 2150
Joined: Tue Jun 30, 2009 6:16 am UTC

Re: Card guessing game

Postby mmmcannibalism » Fri Dec 31, 2010 10:29 pm UTC

I have 0 coding knowledge to do this but

Would the ideal system be to at each turn evaluate the probability of winning; and the probability of a better chance of winning occuring later?

For instance if the first card flipped is black you see that you have X chance of winning. At the same time you evaluate that for a random deck you will have a Y chance of getting an (X+Z) chance (where Y times (X+Z) is greater then X) sometime later on; which means you choose to continue.

Example to explain better

we have 4 cards left and we know two are black and one is red. If a red card is flipped over we have a 33% chance of being right; however, we also have a 66% chance of a 50% chance on the next card. If .66*.5 was greater then 33 we would continue for that opportunity.

This probably gets really complicated since with lots of cards you have to consider the chance of a greater probability, and every way that could happen.
Izawwlgood wrote:I for one would happily live on an island as a fuzzy seal-human.

Oregonaut wrote:Damn fetuses and their terroist plots.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Card guessing game

Postby jestingrabbit » Sat Jan 01, 2011 2:00 am UTC

jjfortherear wrote:My question is, had we been taking the back card every time, it should've been 50 percent, right?


No. As you see more cards, the distribution that you assign to that last card should change. Specifically, if you turn over the seven of diamonds, then the last card can't be the seven of diamonds. If that's the only card that you've revealed, then the last card could be any of 26 black cards, or 25 red cards. Its chance to be red is therefore 25/51. It begins at half-half, but as more information is given, that distribution changes.

mmmcannibalism wrote:Would the ideal system be to at each turn evaluate the probability of winning; and the probability of a better chance of winning occuring later?


Try a few different strategies with a deck with only four cards in it, 2 red and 2 blacks. Spot a pattern. Do the same for 6, and maybe 8. From there you should be able to answer your own question.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Moose Hole
Posts: 398
Joined: Fri Jul 09, 2010 1:34 pm UTC

Re: Card guessing game

Postby Moose Hole » Mon Jan 03, 2011 9:29 pm UTC

aleph_one wrote:What is the optimal winning probability?
I think a lot of the problems in this thread stem from this ambiguous question. It has been shown that there is no optimal strategy. However, is the "winning probability" measured at the beginning of the game or at the current time in the game? I took it to mean at the beginning of the game, in which case it's
Spoiler:
50/50.

aleph_one
Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

Re: Card guessing game

Postby aleph_one » Mon Jan 03, 2011 9:50 pm UTC

The winning probability is that at the start of the game. It is the maximum over all strategies of the probability of that strategy winning on a randomly shuffled deck. The probability of winning at any point in the game (over the distribution of decks conditioned on what you've) has been calculated by imatrendytotebag.
Spoiler:
The winning probability indeed 1/2. Rather than say there's no winning strategy, I'd say that every possible strategy wins with equal probability, so they are all optimal.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 9 guests