Some Days You Can't Lose

So, last week (man, I planned to write more often than this, but blogging is so hard) I wrote about the card flipping problem, and I guess its time to discuss the solution. First though, its probably best to discuss a common "solution" that does not work (well, actually it works, as we shall see, but its not the solution to the problem).

Attempted solution is as follows:

As soon as you have seen more black cards go by than red cards, say stop.

This looks like a good solution, as anytime you say stop you will have a greater than 1/2 chance to win. What exactly is the overall chance to win though? In the case of a 52 card deck, that is very hard to find, so lets try for a 4 card deck.

There are two separate cases where this strategy will say stop.

1. If the first card is black (1/2 chance), you say stop and win 2/3 of the time.

2. If the first card is red (1/2 chance), then you will only say stop if the next two cards are black (1/3 chance), but then you are guaranteed to win.

So far, you win (1/2*2/3+1/2*1/3)=1/2 of the times that you say stop.

OK, what about when you do not say stop? If you reach the end of the deck and have not seen more black cards than red, then you are in trouble, the last card of the deck is guaranteed to be black.

This summarizes the problem that you meet in the 52 card deck. Many games you will say stop at some point and you have a slightly better than 1/2 chance to win, but there will be the occasional game where you do not say stop and you are certain to lose. In the end you come out 50% no matter what.

OK, could you do better? No, as it turns out. The argument can be made with a few simple points:

1. When you say stop, it wouldn't matter if I were to shuffle the deck before that last flip.
2. When you say stop, if instead I just picked a face-down card in the deck from my choosing, it wouldn't change anything
3. When you say stop, I could just deal the next card from the bottom of the deck.

(This argument can be put more succinctly, but I find this method more convincing). So now we have a different game. I will deal cards off the deck until you tell me to stop. When you do so I will show the bottom card of the deck, if it is red you win, if it is black you lose. What is the optimal strategy for this game?

Its pretty easy to see this game is 50-50 no matter what you do. Even if you were trying to lose you couldn't do more than 1/2 the time (of course, in this game trying to win is equivalent to trying to lose the other way). Naturally, at any given moment when you tell me to stop, you might be better or worse than 1/2 (in particular, if you wait until the last card, then you are either 0 or 1), but for anything you try to do, you were 50-50 from the first card.

This realization that sometimes the order doesn't matter for random events can be very useful, and I will probably refer back to it from time to time (though, I can honestly only think of one major instance that I have used it in logic problems).

I have also used this idea in boardgames. In 1960: The Making of the President, there is a point in the game where you draw 3 cubes from a bag to determine the outcome of events. If at least 2 of the cubes come up your colour, then you win the event, but if at least 2 of them come up the opponents colour, then you lose it, either way, the cubes do not get returned to the bag. Not all the events are equal, and you can choose what order they happen in.

Some would argue something about wanting to do the less important event first, so if the opponents cubes come out, you have more of your cubes in the bag for the better event, and I'm sure one could also make some argument for doing the more important event first as well. However, its not hard to show that there is no optimal strategy here. Naturally, if you do the weaker event first and a bunch of your own cubes come out, you will be upset, but a priori all strategies had been the same.