Pick a card!

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]

17 thoughts on “Pick a card!”

  1. 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

    1. 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.

      1. 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.

        1. 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.

          1. 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 greater if 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.

        2. 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!).

          1. 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?

          2. 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…

          3. 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.

          4. 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

          5. 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.

          6. 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).

  2. 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

  3. 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.

  4. 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.

  5. 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.

Leave a Reply to Matthew Monaghan Cancel reply

Your email address will not be published. Required fields are marked *