3
$\begingroup$

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?

  • 0
    Are you assuming that you start with an equal number of red and black cards? Is it possible that all the cards are red?2012-11-09
  • 0
    I have 16 black and 16 red cards just like in a normal card deck.2012-11-09
  • 2
    A normal deck has 52 cards2012-11-09
  • 0
    [List of traditional card and tile packs](http://en.wikipedia.org/wiki/Piquet_deck) I don't find the card game normal2012-11-10

3 Answers 3

2

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

  • 0
    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?2012-11-10
  • 0
    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 argument2012-11-10
  • 0
    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.2012-11-10
  • 0
    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 strategy2012-11-10
  • 0
    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.2012-11-10
  • 0
    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 say2012-11-10
  • 0
    @miracle173 Would you mind telling me what part of my argument was made clearer in the paper, so that I could edit2012-11-10
  • 0
    "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.2012-11-11
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.

  • 0
    What should $E(n,k)$ be? Some kind of expectation value? Are $k,n$ the numbers of black cards / all cards already drawn?2012-11-09
  • 0
    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.2012-11-09
  • 0
    Something like $E(n,k)=\frac{n-k}{n}E(n-1,k)+\frac{k}{n}E(n-1,k-1)$?2012-11-09
  • 0
    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)$.2012-11-09
  • 0
    I'd say $E(n,k)=\frac{k}{n}$ is a closed form, which is probably the wrong solution...2012-11-09
  • 0
    $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.2012-11-09
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\%$.