4

You have a deck of 32 playing cards. Somebody draws one card after another and shows them to you. At any point of time you may bet that the next card is black. If it is indeed black you earn $10, otherwise nothing. If you don't do anything you earn nothing as well. Find the optimal strategy.

In other words you should find the point of time where the quota of remaining red cards in the deck is maximal.

Any hints how to to this?

Emily
  • 35,688
  • 6
  • 93
  • 141
QuasiK
  • 43

3 Answers3

3

I take as additionnal assumption that if you do nothing, you bet on the last card rather than automatically losing.

There is no optimal strategy. Imagine the game this way. Instead of betting on the next card, you bet on the last card. Note that you still interrupt the game at any time you want you just bet on a different card.

The last card has the same probability of being black as the first one on the remaining card since you know nothing of how they are ordered. (i.e. every permutations is possible). The expected number of times you win this game is thus the same as in yours.

When do you win my game? Well you win if your last card is black, which ultimately happens half of the time.

This simple (symmetry) argument shows that the game is fair and there is no optimal stategy

Jean-Sébastien
  • 4,623
  • 1
  • 17
  • 39
  • That the "...last card is black ... ultimately happens half of the time". Thats the thing one has to proof. I do not understand why this can be seen immediately. Can you explain this? – miracle173 Nov 10 '12 at 15:47
  • Take all of the possible permutations of your deck of card. Half of them will have $1$ of the $16$ black cards as last card, the other half will have $1$ one of the $16$ red. It follows from symmetry, but you can prove it with counting argument – Jean-Sébastien Nov 10 '12 at 15:49
  • that is true. but you have sequences of cards that have not the length 32 because you interrupt the game before you draw all cards. – miracle173 Nov 10 '12 at 16:02
  • The game is shuffled at the beginning of the game though, and will have a black card at the end half of the time regardless of your strategy – Jean-Sébastien Nov 10 '12 at 16:22
  • Take a deck of only 4 cards and your bet that the next card is black the first time you have drawn more red(0) than black(1) cards. The possible results: 00,01,1001,1010,1100. The possibility that a sequence ends with 1 is equal that it ends with 0 , because the probability to generate sequence 01 is 1/3, the probability of the other sequences is 1/6.Also you can create a strategy where the decision to stop after the next card not only depends on the cards you have drawn so far but also on the outcome of a random event. I do not see how your arguments consider all this issues. – miracle173 Nov 10 '12 at 16:51
  • Let me direct you to this article , http://www.teorver.ru/newkatalog/1193689162.pdf, perhaps you will find it better phrased than what I said. Look for game 1.5 and its 2.5 solution, which is almost exactly what I've been trying to say – Jean-Sébastien Nov 10 '12 at 17:08
  • @miracle173 Would you mind telling me what part of my argument was made clearer in the paper, so that I could edit – Jean-Sébastien Nov 10 '12 at 18:29
  • "you know nothing of the remaining cards once you stopped the game" confused me most because I know how many red and black cards are remaining. I also was not sure if you are meaning the last card of the whole deck or the last card of the sequence that was generated until you stopped. – miracle173 Nov 11 '12 at 07:43
0

You are looking for an hint or the solution?

Hint: wrote an explicit formula for $E[n,k]$ as a function of $E[n-1,k]$, $E[n-1,k-1]$, $n$ and $k$. Try to find a closed form that satisfy the above equation.

edit: $n$ are the number of cards, and $k$ the number of black ones. The solution works for any number of cards, so there is no need to worry for 32 or 52 decks.

carlop
  • 1,768
  • What should $E(n,k)$ be? Some kind of expectation value? Are $k,n$ the numbers of black cards / all cards already drawn? – QuasiK Nov 09 '12 at 17:34
  • I must have spend few more word, $E[n,k]$ is the expected value for the optimal strategy when we have $n$ cards left, $k$ of them black and $n-k$ red. – carlop Nov 09 '12 at 17:37
  • Something like $E(n,k)=\frac{n-k}{n}E(n-1,k)+\frac{k}{n}E(n-1,k-1)$? – QuasiK Nov 09 '12 at 17:45
  • This is the equation if you always wait, but you should consider that you can bet on the next card, so: $E(n,k)=max(k/n, \frac{n-k}{n}E(n-1,k)+\frac{k}{n}E(n-1,k-1)$. Now you can try to find a closed form for $E(n,k)$. – carlop Nov 09 '12 at 17:54
  • I'd say $E(n,k)=\frac{k}{n}$ is a closed form, which is probably the wrong solution... – QuasiK Nov 09 '12 at 18:16
  • $k/n$ is actualy the solution, so every strategy that sooner or later bet (skip the last bet is the only error you can do) is optimal. Another reasoning that you can do is @Jean-Sébastien one. – carlop Nov 09 '12 at 18:29
0

You may make a bet at any time; in particular, you may either make a bet when there are an odd number of remaining cards or an even number of remaining cards.

With this in mind, we will prove the claim that no strategy exists which can make the chances of winning greater than $50\%$, by considering $2$ cases. For each, we will look at $P(r,b)$ where $r$ and $b$ denote the number of red and black cards remaining, so that $P(r,b)$ is the probability that $r$ red cards remain and $b$ black cards. Obviously, the chances of winning are greater than $50\%$ if $P(r>b) > P(b>r)$.

Case $1$: The number of remaining cards is odd (say, $2n+1$).

Observe that $P(0,2n+1) = P(2n+1,0)$. [It's just as likely to have no black cards as it is to have no red cards]. Also $P(1,2n) = P(2n,1)$, and so on until (and including) $P(n,n+1) = P(n+1,n)$. In total, $P(r>b) = P(b>r)$, so the odds of winning are not greater than $50\%$.

Case $2$: The number of remaining cards is even (say, $2n+2$).

Using reasoning similar to Case $1$, we have $P(0,2n+2) = P(2n+2,0); P(1,2n+1) = P(2n+1, 1)$; and so on until (and including) $P(n,n+2) = P(n+2,n)$. For all these possible outcomes, $P(r>b) = P(b>r)$, so the chance of winning is not greater than $50\%$.

The only distinction in this case is the outcome where $(r,b) = (n+1,n+1)$. Sadly this does not help our chances. Since the number of cards remaining is equal for each suit, our probability of winning is still $50\%$.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
Greg Hudgens
  • 31