# finding the optimal strategy

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? - Are you assuming that you start with an equal number of red and black cards? Is it possible that all the cards are red? – Jonathan Christensen Nov 9 '12 at 16:44 I have 16 black and 16 red cards just like in a normal card deck. – QuasiK Nov 9 '12 at 17:03 A normal deck has 52 cards – i. m. soloveichik Nov 9 '12 at 17:20 List of traditional card and tile packs I don't find the card game normal – miracle173 Nov 10 '12 at 6:22 add comment ## 2 Answers 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 - 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 show 5 more comments 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. - 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 9 '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 9 '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 9 '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 9 '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 9 '12 at 18:16
show 1 more comment