This Riddler puzzle is about a card game where the goal is to find the largest card.

From a shuffled deck of 100 cards that are numbered 1 to 100, you are dealt 10 cards face down. You turn the cards over one by one. After each card, you must decide whether to end the game. If you end the game on the highest card in the hand you were dealt, you win; otherwise, you lose.

What is the strategy that optimizes your chances of winning? How does the strategy change as the sizes of the deck and the hand are changed?

Here is my solution:

[Show Solution]

### Approximate solution

Let’s suppose that the deck has $n$ cards in it, and we are dealt $k$ cards from the deck. Every time a card is flipped, we must decide whether to keep playing or to stop. Suppose we have flipped over $m$ cards already and the largest card flipped so far has a value of $a$. Some quick observations:

- If the last card we flipped has value smaller than $a$, then we must clearly keep flipping cards, for we would definitely lose if we stopped playing now.
- Assuming the last card we flipped has the largest value ($a$), we must evaluate the probability that the remaining $k-m$ cards are each smaller than $a$ (in other words, the probability that $a$ is the winner). We should compare this probability to the probability that we will win if we continue playing. Whichever is highest will dictate the optimal course of action.

One possible decision heuristic is to stop if the probability that the current card is a winner is greater than $1/2$ and to keep playing otherwise. This turns out to be a suboptimal strategy because our chances of winning might be *even less* if we keep playing! In other words, it could happen that we have a 49% chance of winning if we stop now but only a 45% chance of winning if we keep playing; in such a case, we should stop now and cut our losses. That being said, this suboptimal strategy is a very good approximation to the optimal strategy (and very easy to compute!) so let’s work it out.

Each of the $m$ cards we’ve flipped over so far is distinct and less than or equal to $a$. If the current card $a$ is the winner, then the remaining $k-m$ cards must all be chosen among the $a-m$ cards that are less than or equal to $a$. This can be done in $a-m \choose k-m$ ways. In total, there are $n-m \choose k-m$ ways of choosing the remaining cards. Therefore, we should stop playing if

\[

\frac{a-m \choose k-m}{n-m \choose k-m} \ge \frac{1}{2}

\]Clearly, this will be satisfied for $a$ sufficiently large, so our optimal decision rule is a *threshold rule*. There is no closed-form expression for the threshold value of $a$, but it’s straightforward to compute numerically. Here is a plot of the approximate decision rule for the case $n=100$, $k=10$.

The triangular white region in the lower corner corresponds to the case $a < m$, which can't occur because $a$ must be the largest number seen so far and all numbers must be distinct.

### Exact solution

To get an exact solution, we’ll use dynamic programming. Let the cards be numbered $\{1,2,\dots,n\}$ and let $k$ be the number of face-down cards at the start of the game. In general, one might expect an optimal strategy to depend on the individual values of all the cards revealed thus far. This is not the case. It turns out that the optimal strategy only depends on:

- How many cards we’ve seen so far (we’ll call this $m$)
- The highest-valued card we’ve seen so far (we’ll call this $a$)
- Whether the last card turned over is the largest so far or not.

We’ll define two functions, $V^\text{lo}_m(a)$ and $V^\text{hi}_m(a)$, to record the probability of winning the game in the case where the latest card we turned over is low or high, respectively.

**Base case:** Suppose $m=k$, so we have just flipped over the final card. The game automatically ends and we have no decisions to make. We win if the card we flipped over is the highest numbered card. In other words:

\[

\begin{aligned}

V^\text{lo}_k(a) &= 0 \\

V^\text{hi}_k(a) &= 1

\end{aligned}\qquad\text{for }a = 1,\dots,n

\]

**Recursion:** Now suppose that we’re $m$ steps into the game. Let’s start with the case of a low flipped card. Here, we’ll lose for sure if we stop the game. So we must keep playing. We’ll assume $y \in S$ is the next card we flip over. Here, $S \subseteq \{1,\dots,n\}$ is the set of cards we haven’t seen yet. Note that $|S| = n-m$ because we have flipped over $m$ cards so far. Any of these $n-m$ remaining cards could be flipped over next with equal probability. Let’s treat the cases $y < a$ and $y > a$ separately:

\begin{align}

V^\text{lo}_m(a) &= \frac{1}{n-m}\biggl( \sum_{y\in S,\,y < a} V^\text{lo}_{m+1}(a) + \sum_{y\in S,\,y > a} V^\text{hi}_{m+1}(y) \biggr) \\

&= \frac{1}{n-m}\biggl( (a-m) V^\text{lo}_{m+1}(a) + \sum_{y=a+1}^n V^\text{hi}_{m+1}(y) \biggr)

\end{align}In the last step, we use the fact that there are precisely $a-m$ terms in $V^\text{lo}$ sum, which doesn’t depend on $y$. In the $V^\text{hi}$ sum, we’re summing over all values larger than $a$, and no such values have been used yet.

For the case of a high flipped card, we can choose to either stop the game or keep playing. If we stop the game, we will win if the remaining $k-m$ cards all happen to be smaller than $a$, our current high card. There are $a-m$ cards that satisfy this property and $n-m$ cards left total, so the probability of winning is ${a-m \choose k-m}/{n-m \choose k-m}$. If we decide to keep playing instead, we get the same answer as in the low case. Therefore, our recursion is:

\[

V^\text{hi}_m(a) = \max\biggl\{ \underbrace{\frac{{a-m \choose k-m}}{{n-m \choose k-m}}}_{\text{STOP}}, \,

\underbrace{V^\text{lo}_m(a)}_{\text{PLAY}} \biggr\}\qquad\text{for }a=1,\dots,n

\]At this point, it’s not possible to proceed any further without resorting to numerical computations. The good news is that these recursions are relatively easy to tabulate numerically; we can store all relevant probabilities in two matrices $V^\text{lo},V^\text{hi} \in \mathbb{R}^{k\times n}$ and we can compute everything in $\mathcal{O}(n^2k)$.

Here is a plot of the optimal decision rule for the case $n=100$, $k=10$.

As we can see, this plot is very similar to the approximate rule. Here is a table of the threshold values for comparison:

Cards flipped | Approximate Threshold | Optimal Threshold |
---|---|---|

1 | 93 | 93 |

2 | 93 | 92 |

3 | 92 | 91 |

4 | 90 | 89 |

5 | 88 | 87 |

6 | 86 | 84 |

7 | 82 | 80 |

8 | 74 | 72 |

9 | 55 | 55 |

10 | 10 | 10 |

This means that e.g. if our ninth card is $55$ or greater, we should stop playing. Note that if we make it to the 10th turn and our final flipped card is still a contender (i.e. the largest we’ve seen so far), then that card cannot have a value less than $10$ and we automatically win.

### Probability of winning

So how do we compute the actual probability of winning? We already have! If we have recursed all the way to $m=1$, then $V^\text{hi}_1(b)$ tells us the probability of winning given that the first card we flipped over was $b$ (and, of course, it was our highest card). Since all cards are equally likely first cards, we have:

$\displaystyle

\mathbb{P}(\text{winning}) = \frac{1}{n}\sum_{b=1}^n V_1^\text{hi}(b) = V_0^\text{hi}(1)

$

For the case $n=100$ and $k=10$, the probability of winning is 62.19%.

### Limiting cases

We can easily compute what happens if we add more cards. Let’s fix $k=10$ and try $n=1000$.

As we can see, things don’t look that much different as we make $n$ large. We can approximate this limiting shape by taking the limit $n\to\infty$ while holding $a$ as some fixed fraction of $n$ and using our approximate strategy instead of the optimal one:

\begin{align}

\frac{a-m \choose k-m}{n-m \choose k-m}

= \prod_{j=1}^{k-m} \frac{a-m+1-j}{n-m+1-j}

\approx \prod_{j=1}^{k-m} \frac{a}{n}

= \left(\frac{a}{n}\right)^{k-m}

\end{align}Therefore the threshold (when this probability hits $1/2$) occurs when:

\[

a \approx n\,2^{-\frac{1}{k-m}}

\]We can overlay the limiting case formula with the actual one to see how well they match. Here is an example with $n=10000$ and $k=40$:

It’s a pretty good fit, with the thresholds for the optimal strategy being slightly lower than the optimal ones. Increasing $k$ is also straightforward, and simply amounts to shifting the above pictures to the right!

**Note:** computing the ratio of binomial coefficients can be difficult if done naively, since it involves the ratio of two very large numbers. The method I used in producing my plots was to convert the expression into a product:

\[

\frac{a-m \choose k-m}{n-m \choose k-m}

= \prod_{j=1}^{k-m} \frac{a-m+1-j}{n-m+1-j}

\]then computing each term of the product and multiplying them together.

Hi Laurent,

This is not the same strategy I find. I don’t understand how you arrived at the criterion that a win probability of 1/2 or higher means you should stop, and less than 1/2 means you should continue playing.

I find that one should compute the probability of winning if I don’t stop, which I will write as

P(n,k,m,a)

(the probability that in an n-card game with k cards drawn, when the m’th card is flipped and the maximum value so far is a, that the optimum strategy for the remaining k-m cards will result in winning).

Then I have to compare the chance of winning if I stop, which you compute correctly, to P(n,k,m,a). In some cases P(..) is enough below 1/2 that you should stop even if the chance of winning is slightly below 1/2. My (horribly inefficient) code is at

https://theorie.ikp.physik.tu-darmstadt.de/qcd/ncards.c

see if it gives slightly different winning probabilities than your approach.

Guy Moore

I really enjoyed reading your solution. As always, I walked away thinking about several things I hadn’t considered.

I agree with Guy Moore. Consider the case where n=50 and k=4. If the first card is 40 and you end the game, the probability of winning is Comb(39,3)/Comb(49,3) = 0.4960. Since this is less than 0.5, by your logic you should continue the game.

But if you continue the game, your probability of winning actually decreases. If your first card is 40, the total number of ways to win is sum(Perm(i-2,2),i,41,50) + 39*sum(Perm(i-3,1),i,41,50) + 39*38*10 = 49965. The probability of winning is 49965/P(49,3) = 0.4520.

Empirically the 0.5 criteria is a good approximation of the solution, and I came up with similar thresholds through simulation. I think you need to compare the probability of winning if you stop the game to the probability of winning if you continue the game to get the exact solution though.

Thanks Guy and Matthew for the comments. You’re both right. I was correct in saying that you should stop if P > 1/2 but hasty in concluding that you should always play on if P < 1/2. I'll think a bit more on this and hopefully revise my solution soon.

I updated my blog post. I now compute the solution approximately and exactly and compare the two. It turns out the 1/2 heuristic is quite good! Thanks for all the feedback!

Edit: Thanks Gabe! I made the change you suggested and edited the text to clarify.

As you (correctly) noted in your previous comment, you should always stop if p>1/2, and sometimes even if p<1/2. However the third paragraph of your solution reads:

"[The 1/2 heuristic] turns out to be a suboptimal strategy because our chances of winning might be

even greaterif we keep playing!"This seems to imply the opposite claim: that you should always continue if p<1/2, and sometimes even if p>1/2. If you changed it to either “…our chances of losing…” or “…might be

even less…” (not both, of course), it would be correct.I found an easily computable formula for the probability of winning if you continue:

P(a,m,k,n) = sum[prod[j,{j,a-i+2,a-m}]*sum[Perm(j-i,k-i),{j,a+1,n}],{i,m+1,k}] / Perm(n-m,k-m)

Here is how I arrived at this formula. If you continue playing after the mth card, there are k-m ways you can win:

1.) The m+1th card is between a+1 and n, you stop, and all the other cards are lower. There are Perm(a+1-m-1,k-m-1) + … + Perm(n-m-1,k-m-1) ways this can occur.

2.) The m+1th card is less than a, the m+2th card is between a+1 and n, you stop, and all the other cards are lower. There are (a-m) * (Perm(a+1-m-2,k-m-2) + … + Perm(n-m-2,k-m-2)) ways this can occur.

3.) The m+1th and m+2th cards are less than a, the m+3th card is between a+1 and n, you stop, and all the other cards are lower. There are (a-m) * (a-m-1) * (Perm(a+1-m-3,k-m-3) + … + Perm(n-m-3,k-m-3)) ways this can occur.

4.) etc.

The formula sums all these occurrences and divides by the number of hand permutations to calculate the probability of winning. The thresholds occur when the probability of winning by stopping is less than the probability of winning by continuing. Using this formula and your formula for the probability of winning if you stop, I came up with the exact same thresholds as you did in your revised post (which was excellent!).

I don’t quite follow — how do you account for stopping vs not stopping? It seems that in 1.), you count the number of ways that the next card flipped over is a winner. But shouldn’t you only be counting these cases if you also decide to stop at that point? Shouldn’t the decision rule come into play here?

For example, I could win if the (m+1)st card is greater than a, but I keep playing anyway, and then the (m+2)nd card is greater still, I stop, and all subsequent cards are smaller. The probability of winning should depend on the rule I’m using to decide when to stop, no?

You make a great point: “For example, I could win if the (m+1)st card is greater than a, but I keep playing anyway, and then the (m+2)nd card is greater still, I stop, and all subsequent cards are smaller.”

Consider the n=100 and k=10 and m=1 case. Let’s say I’ve used the argument I’m about to make to rule out 100 to 94 as the optimal threshold, and I want to test 93. Intuitively, the stopping thresholds will decrease as more cards are played. So if the first card is 93 and I continue playing, all the subsequent thresholds must be ≤94. Therefore, if I get a higher card (94 to 100) on the second card, I MUST stop playing because the second card will be equal to or exceed the second threshold. I won’t have a choice to continue playing and get a higher card later on. The next eight cards must all be lower than the second to win. Similarly, if the second card is lower (1 to 92) and the third card is higher (94 to 100), the third card will exceed the third threshold and I will have to stop and hope the next seven cards are lower. And so on and so forth…

Just because I keep playing, it doesn’t mean my current number is right at the threshold… For example, suppose you’ve decided that the thresholds for m=1,2,3,4,5 are:

90, 80, 70, 60, 50, 0 (these aren’t the true thresholds, of course).

Now suppose the flipped-over cards are:

5, 25, 20, 32, 62, 55

Then, the threshold rule will make me continue playing until I reach 62, at which point I stop because 62 > 50. In this example, I win the game. This case isn’t included as a possible way of winning according to your previous post. After flipping my first card, I had a=5. The second card had a larger value but I didn’t stop. In fact, “a” changed to 25, then to 32, then to 62, at which point I finally stopped.

Yeah I don’t think I’m explaining myself well… or my logic could certainly be flawed 🙂

Out of curiosity, can you check to see if we arrive at the exact same thresholds for some arbitrary case? For example when n = 937 and k = 23 I get the following thresholds: 905, 903, 902, 900, 898, 895, 893, 890, 887, 883, 879, 874, 868, 860, 852, 840, 826, 806, 777, 732, 654, 480

Thanks for all the replies, and for what it’s worth here’s a link to my Matlab code.

https://www.dropbox.com/s/u6b7adc614p99yt/riddler.m?dl=0

I obtained the exact same threshold rule as you did for the case n=937, k=23. There must be something I’m missing because it seems like you’re not counting all possible cases… Can we try one more? for n=25, k=13, I get: 24, 24, 24, 24, 24, 24, 24, 23, 23, 22, 21, 19.

I get the exact same threshold values as you. Let me try to make my case one more time:

For n=100 and k=10, let’s assume the first threshold is 93. This implies that the probability of winning by stopping at 93 is greater than the probability of winning by playing at 93. Mathematically speaking: P_stop(n=100, k=10, m=1, a=93) > P_play(100,10,1,93). For compactness, I’ll write this as P_stop(93) > P_play(93). It also implies that P_play(92) > P_stop(92). In other words, it is better to play at 92 than it is to stop.

We agree that P_stop(92) = C(92-1,10-1)/C(100-1,10-1) = 0.4528. But what about P_play(92)? Since we are right below the first threshold and we know all subsequent thresholds will be ≤93, any future card >92 will force us to stop the game. The only way to win is to get exactly one card greater than 92, stop, and hope all the other cards are lower. Using my previously posted formula, P_play(92) = 0.4659. Indeed, P_play(92) > P_stop(92).

We must also check that P_stop(93) > P_play(93). Sure enough, P_stop(93) = 0.5019 and P_play(93) = 0.4346. Since the transition in best strategy occurs between 92 and 93, 93 must be the threshold.

This is my approach in a nutshell. My code searches for the threshold value ‘a’ that satisfies P_stop(a) > P_play(a) and P_play(a-1) > P_stop(a-1).

Nicely done. I did a similar thing (https://hectorpefo.github.io/2017-04-22-highest-card/) that produces the same calculated probability of winning and the same thresholds as your solution. Frustratingly, though, my Monte Carlo sim using those thresholds gives a lower probability of winning, around .595. So something’s off somewhere…probably in the sim? But it’s so simple.

https://github.com/hectorpefo/hectorpefo.github.io/blob/master/_includes/PickACard538.py

Never mind; sim was indeed at fault!

Sorry to spam your comment section, but I found an exact analytic expression for the threshold values when n approaches infinity. For an infinite number of cards, let the card values range from [0,1]. Define q=k-m and let x be the threshold value as a function of q. The threshold value is the solution to:

z(q)/q! * x^q – sum[x^(q-i)/i,{i,1,q}] = 0 where z(1)=2 and z(i)=i*z(i-1)+(i-1)!

The first couple threshold values are: 0.50000, 0.68990, 0.77585, 0.82459, 0.85595, …

These threshold values line up nicely (3-4 digits of accuracy) to the threshold values when n > 10,000.

Laurent and Hector,

The difference between the approximate and ‘optimal’ answers are small. Have you tested them (and some in between possibilities) by simulations. I could try but I’m not set up to do so easily.

Hi Laurent !!

Hope, everything is fine. I really enjoyed while reading your solution. Recursion is one of my favorite topic and i found very interesting while reading that particular blog.

Thanks.