How To Avoid A Bar Tab [Solution]

Solution for the week of 3/23

What a fun, devilish problem from Alex! For a quick refresher…

After a weeks long bar crawl, you and your friends are exhausted and have run up an enormous tab. Your bartender Alex—an avid puzzler himself—overhears your complaining and proposes a game that gives you all the chance to zero out your tab if you win. But if you lose, your tab doubles. The game goes as follows.

You begin with a two card deck consisting of one red and one black card. On each turn:

1) You flip a fair coin. If it lands heads, you add a black card to the pile. If it lands tails, no new card is added.

2) You shuffle the cards in the pile

3) You randomly select one card from the pile and observe it. If it’s red, the game is over. If its black, you return the card to the deck and go back step 1 repeating the process.

Alex tells you that you need to make it a certain number of turns without drawing a red card in order to win. Before he tells you how many rounds you need to win, you first want to compute how long this game is expected to last so that you can tell whether you should take the bet or not. So the question for this week is:

How many turns is this game expected to last?

After reading the problem, I’m guessing many of you did exactly what I did; jump immediately to a harmonic series and assume the expectation was unbounded. But not so fast! As solvers

Seth Cohen

and

Benjamin Phillabaum

correctly determined, this isn’t quite a harmonic series and it turns out the seemingly minor variation that the coin toss introduces is the difference between a convergent and divergent series!

First, let’s start with a simpler version of the puzzle. Image there is no coin and we will always just add a black card each turn. Let’s also define E[N] to the expected number of turns when the deck has N cards. For this game, we can define the following recursive relationship

\(\mathbb{E}[N] = 1 + \frac{N}{N+1} \mathbb{E}[N+1]\)

No matter what we will add a card next round. Then, we will either terminate (draw a red card) on the next round or not (draw a black card). The probability of not terminating is N/(N+1). In that case, we will also be continuing the game with N+1 cards.

Now, if we iteratively substitute E[N+1], E[N+2], etc. k times and do some simplification, we get

\(\mathbb{E}[N] = \sum_{m=0}^{k-1} \frac{N}{N+m} + \frac{N}{N+k} \mathbb{E}[N+k]\)

Looking at the first term, we can already notice that if we take the limit as k goes to infinity, it becomes is a variation of the harmonic series, which is known to diverge. So this expectation is unbounded.

But of course, this isn’t quite the game we’re playing—we have to reintroduce the coin flip element. But now that we’ve set up the simpler game, it should be pretty easy to modify it for our current game.

\(\mathbb{E}[N] = 1 + \frac{1}{2} \frac{N-1}{N} \mathbb{E}[N] + \frac{1}{2} \frac{N}{N+1} \mathbb{E}[N+1]\)

Again, we always advance to the next round but if we get tails we don’t add a card and there’s a (N-1)/N chance of drawing a black card, in which case the game continues with N cards. If you flip heads, you add a black card so now there’s a N/(N+1) chance of drawing a black card in which case the game proceeds with N+1 cards.

After some algebra and rearranging we get

\(\mathbb{E}[N] = \frac{2N}{N+1} + \left( \frac{N}{N+1} \right)^2 \mathbb{E}[N+1]\)

We again iteratively substitute E[N+1], E[N+2], etc. and do some simplification to get

\(\mathbb{E} = \sum_{k=0}^{\infty} \frac{2(N+k)}{N+k+1} \prod_{i=0}^{k-1} \left( \frac{N+i}{N+i+1} \right)^2\)

This looks a little messy but there are a few simplifications we can make to reign it in. First, let’s note that the numerator and denominator of the product term have a telescoping structure (i.e. the denominator of one term is the same as the numerator of its successor term). As such, we can simplify that term significantly.

\(\mathbb{E}[N] = \sum_{k=0}^{\infty} \frac{2(N+k)}{N+k+1} \left( \frac{N}{N+k} \right)^2 = \sum_{k=0}^{\infty} \frac{2N^2}{(N+k+1)(N+l)}\)

Leveraging a little fraction decomposition…

\(2N^2 \sum_{k=0}^{\infty} \frac{1}{(N+k+1)(N+l)} = 2N^2 \sum_{k=0}^{\infty} \left( \frac{1}{N+k} - \frac{1}{N+k+1} \right)\)

This is also a telescoping series! We are left with the first and last term—which in this case 1/(N+k+1) becomes 0 at k=infinity so we’re left with

\(\mathbb{E}[N] = \frac{2N^2}{N} = 2N\)

And of course, our starting number of cards was N=2 so 4 is our answer!

We can verify that with a bit of simulation, which I’ve posted here.

Also, I encourage you to check out

Benjamin Phillabaum

’s solution. He took a very different approach and still arrived at the correct solution. He managed to construct equations using the probability of the game ending on the m-th round (instead of using expectations as we did).

---

What a ride! A beautiful subtlety in divergence criteria, two every elegant telescoping series simplifications, and ending up with an incredibly tidy solution. Well done Alex! Well done. This is precisely why I invite readers to share their ideas for puzzles.

As always, please comment with any thoughts or feedback you had on this problem or if you approached it differently. And please use the comments to give some appreciation to Alex for his excellent puzzle. Thanks for reading!