# Winning strategy for game guessing if next number is prime

I've come across an intriguing card game where a deck is used with cards numbered from $$1$$ to $$N$$.

The game proceeds as follows: the dealer draws cards one by one from the deck and shows the number on each card. At any point in the game, even before the first card is shown, a player can say "stop". If the number on the next card drawn is a prime number, the player wins; if it's not, the player loses. The cards in the deck are shuffled randomly, so there's no way to predict the order of the cards.

I'm trying to determine the best strategy for this game to maximise the chances of winning. Also, how would you calculate the probability of winning with this strategy for a given number of cards, $$N$$, in the deck?

Some clarifications:

• The number 1 is not considered a prime.
• You can see and remember the cards that have been drawn out, which can inform your strategy.
• Knowing the number $$N$$, you can identify all the prime numbers within that range beforehand.
• If all cards are drawn and you haven't said "stop" before the last one (even if it's not), you lose.

Additionally, the author of the problem mentioned that there should be a strategy that optimizes the probability of winning.

• Comments have been moved to chat; please do not continue the discussion here. Before posting a comment below this one, please review the purposes of comments. Comments that do not request clarification or suggest improvements usually belong as an answer, on Mathematics Meta, or in Mathematics Chat. Comments continuing discussion may be removed. Commented Dec 16, 2023 at 23:41
• @XanderHenderson - It looked to me as if some of the comments asked for clarifications and the question was edited to include those clarifications. Commented Dec 17, 2023 at 2:20

More generally, suppose that there are $$n$$ cards total in the deck, where that $$k$$ of the cards are considered to be good, while the remaining $$n-k$$ cards are bad. The goal is the same; the deck is shuffled, and as the cards are flipped from the deck, you have the option to call "stop" at any time. You win as long as the next card dealt is good. What is the optimal strategy?

Furthermore, let us modify the rules to say that, when there is only one card left, you must call stop. A player who does not call stop before the last card automatically loses, so this modification makes no difference to an optimal player.

It turns out that every strategy is the optimal strategy.

Theorem: Every strategy for this game has a probability of winning of $$k/n$$.

Therefore, to answer your question, the probability of winning is the number of primes in $$\{1,\dots,N\}$$, divided by $$N$$.

### Proof 1: Clever insight

Consider this modification of the game. Suppose that, when you call stop, instead of winning when the next card dealt is good, you win if the bottom card of the deck is good. This is a silly game, because it does not matter when you call "stop." You will always win if and only if the bottom card is good. For the modified game, the probability of winning is $$k/n$$.

However, this game has the exact same probability for winning as the original. The point is that, after calling "stop", both the next card and the last cards have the same same random chance of being good, because of the symmetry of the shuffled deck. Therefore, it follows the original game has the same probability of winning.

### Proof 2: Induction

We prove, by induction on $$n$$, that for all $$k\in \{0,1,\dots,n\}$$, the probability of winning is $$k/n$$ for all strategies in an $$n$$-card deck with $$k$$ good cards.

The base case of $$n=1$$ is obvious. Assuming that the statement is true for $$n$$, where $$n\ge 1$$, we prove it for $$n+1$$ as follows: \begin{align} P(\text{win}) &=P(\text{win}\mid \text{first card is good})P(\text{first card good}) \\&\quad +P(\text{win}\mid \text{first card is bad})P(\text{first card bad}) \\&=\frac{k-1}{n-1}\cdot \frac{k}{n}+\frac{k}{n-1}\cdot \frac{n-k}{n}=\frac{k}n. \end{align} This completes the proof by induction.

### Proof 3: Martingale

For each $$k\in \{0,1,\dots,n-1\}$$, let $$X_k$$ be the proportion of good cards among the unseen cards after $$k$$ cards have been seen. So, $$X_0=k/n$$, and $$X_1$$ is either equal to $$k/(n-1)$$ or $$(k-1)/(n-1)$$.

Imagine the player is following a particular strategy. Let $$T$$ be the turn number that the player calls stop, under that strategy. The proportion of good cards at the time of the stop call is $$X_T$$, so $$X_T$$ is the probability the player wins (conditional on $$T$$). We just need to evaluate $$\mathbb E[X_T]$$, which is the unconditional probability of the strategy winning.

The sequence $$X_0,X_1,\dots,X_{n-1}$$ is a martingale, with respect to the natural filtration. To prove this, we must show that $$\mathbb E[X_{k+1}\mid X_k]=X_k$$ for all $$k$$. Indeed, given $$X_k$$, there are two possibilities; either you next draw a good card with probability $$X_k$$, in which case $$X_{k+1}$$ decreases to $$\frac{(n-k)X_k-1}{n-k-1}$$, or you draw a bad card with probability $$(1-X_k)$$, in which case $$X_{k+1}$$ increase to $$\frac{(n-k)X_k}{n-k-1}$$. Therefore, $$\mathbb E[X_{k+1}\mid X_k]= X_k\cdot \frac{(n-k)X_k-1}{n-k-1}+\left(1-{X_k}\right)\frac{(n-k)X_k}{n-k-1}={X_k}.$$ Since the sequence is a martingale, and since $$T$$ is bounded, we can use the optional stopping theorem to conclude that $$\mathbb E[X_T]=\mathbb E[X_0]=k/n$$. Therefore, every strategy has a probability of success of $$k/n$$.

• To be unnecessarily pedantic, every strategy that definitely calls stop before the deck is exhausted is equivalent. The game as described allows for strategies that (foolishly) sometimes don't call stop, which are strictly worse. Commented Dec 15, 2023 at 1:47
• I first heard about this problem/solution from Games People Don't Play - Peter Winkler. It's only 12 pages long and contains a number of games with similarly surprising solutions. (Unfortunately I can only find the postscript version, not a PDF) Commented Dec 15, 2023 at 10:01
• @BlueRaja-DannyPflughoeft If that helps, "Games People Don't Play" by Peter Winkler can be found as a chapter inside "Puzzler's tribute: A feast for the mind" edited by David Wolfe and Tom Rodgers
– Stef
Commented Dec 15, 2023 at 13:29
• Commented Dec 15, 2023 at 17:50
• @Michael, "most" in the sense of more than half and less than all, but "not enough" to change the overall probability of winning compared to stopping right at the start. Commented Dec 17, 2023 at 2:19