Another week, another Riddler Express:
Take a standard deck of cards, and pull out the numbered cards from one suit (the cards 2 through 10). Shuffle them, and then lay them face down in a row. Flip over the first card. Now guess whether the next card in the row is bigger or smaller. If you’re right, keep going.
If you play this game optimally, what’s the probability that you can get to the end without making any mistakes?
Extra credit: What if there were more cards — 2 through 20, or 2 through 100? How do your chances of getting to the end change?
The optimal strategy is presumably obvious, but I guess I should get it out of the way - you should always guess higher when there are more cards higher than your current card, and you should always guess lower when there are more cards lower than your current card.
With 2 cards you are guaranteed to succeed.
With 3 cards, if the first card is a 1 or a 3 (2/3 chance), you just reduce to the 2 card case, and always succeed. If it's a 2 (1/3 chance), then you have a 50% chance of getting the first guess right, and then you're in the 2 card case. So that's 2/3 + 1/2*2/3 = 5/6 chance of success.
Let's do 4 cards. There are effectively 2 cases (a 1 and a 4 are the same, and a 2 and a 3 are the same).
If you draw a 1, then you're in the 3 card case, and you succeed with probability 5/6.
If you draw a 2, then there's a 2/3 chance that you get your first guess right, and after that, you either have a 100% chance of success (the next card is a 4) or a 1/2 chance (the next card is a 3, and you have to guess whether the third card is a 1 or a 4). That's 2/3*(1/2+ 1/2*1/2) = 2/3*3/4 = 1/2 chance of success.
A 3 is clearly the same as a 2, so that's
1/2 * 5/6 + 1/2 * 1/2 = 8/12, or 2/3 chance of success.
Note that you get your first guess right fully 5/6 of the time (1/2 the time you draw a 1 or a 4, and then you get it right 2/3 of the remaining times, for 1/2 + 2/3*1/2 = 5/6), and then you're in a 3 card case, so you might intuitively think that your probability of success is 5/6 * 5/6 = 25/36, but this isn't quite right. When your first guess is right, you are less likely to be at one of the 'ends' of the deck, so your second guess is harder on average when the first guess is right.
I can't figure out how to solve this analytically, so I went ahead and coded it up:
https://github.com/johnfaben/riddler/tree/master/HigherOrLower
See the graph on the right for probabilities of succeeding given various numbers of cards in the initial deck. Note that for some reason the initial deck the Riddler question started with was 9 cards (2-10), so the answer would be ~0.17. The answers to the 'stretch questions are:
2-20: "~0.08%" (I printed 20 cards instead of 19 on the graph, and I can't be bothered to change it...)
2-100: "I am not running a simulation long enough to actually get any results - as close to zero as makes no difference"
How do your chances of getting to the end change? Roughly, you increase the chance of failing by 0.75 for each extra card you add (in the limit, your chances of success on the first card approaches 0.75, as you have a 50% chance if you're in the middle, a 100% chance if you're at one of the ends, and the chances change linearly between those two, and in the limit, the effect of landing in the 'wrong' half of the draw when you get the first guess right will shrink, as almost everything is 'near the middle'). So your chances of success are roughly proportional to 0.75^n. To illustrate this, I plotted 0.75^n on the graph as well (that's the blue line).
Note that it would be relatively easy to get an exact answer for the 9 card question - there are after all less than 1 billion orders of 9 cards, so you could just work out your chances of success for each of them, but I am not going to do that, mostly because my code would require a significant rework to handle taking the permutation as an input, rather than the number of cards, but also because that wouldn't help us with the 20 card case, and because the curve above is smooth enough that I'm pretty confident the simulations are doing their job.
With 2 cards you are guaranteed to succeed.
With 3 cards, if the first card is a 1 or a 3 (2/3 chance), you just reduce to the 2 card case, and always succeed. If it's a 2 (1/3 chance), then you have a 50% chance of getting the first guess right, and then you're in the 2 card case. So that's 2/3 + 1/2*2/3 = 5/6 chance of success.
Let's do 4 cards. There are effectively 2 cases (a 1 and a 4 are the same, and a 2 and a 3 are the same).
If you draw a 1, then you're in the 3 card case, and you succeed with probability 5/6.
If you draw a 2, then there's a 2/3 chance that you get your first guess right, and after that, you either have a 100% chance of success (the next card is a 4) or a 1/2 chance (the next card is a 3, and you have to guess whether the third card is a 1 or a 4). That's 2/3*(1/2+ 1/2*1/2) = 2/3*3/4 = 1/2 chance of success.
A 3 is clearly the same as a 2, so that's
1/2 * 5/6 + 1/2 * 1/2 = 8/12, or 2/3 chance of success.
Note that you get your first guess right fully 5/6 of the time (1/2 the time you draw a 1 or a 4, and then you get it right 2/3 of the remaining times, for 1/2 + 2/3*1/2 = 5/6), and then you're in a 3 card case, so you might intuitively think that your probability of success is 5/6 * 5/6 = 25/36, but this isn't quite right. When your first guess is right, you are less likely to be at one of the 'ends' of the deck, so your second guess is harder on average when the first guess is right.
I can't figure out how to solve this analytically, so I went ahead and coded it up:
https://github.com/johnfaben/riddler/tree/master/HigherOrLower
See the graph on the right for probabilities of succeeding given various numbers of cards in the initial deck. Note that for some reason the initial deck the Riddler question started with was 9 cards (2-10), so the answer would be ~0.17. The answers to the 'stretch questions are:
2-20: "~0.08%" (I printed 20 cards instead of 19 on the graph, and I can't be bothered to change it...)
2-100: "I am not running a simulation long enough to actually get any results - as close to zero as makes no difference"
How do your chances of getting to the end change? Roughly, you increase the chance of failing by 0.75 for each extra card you add (in the limit, your chances of success on the first card approaches 0.75, as you have a 50% chance if you're in the middle, a 100% chance if you're at one of the ends, and the chances change linearly between those two, and in the limit, the effect of landing in the 'wrong' half of the draw when you get the first guess right will shrink, as almost everything is 'near the middle'). So your chances of success are roughly proportional to 0.75^n. To illustrate this, I plotted 0.75^n on the graph as well (that's the blue line).
Note that it would be relatively easy to get an exact answer for the 9 card question - there are after all less than 1 billion orders of 9 cards, so you could just work out your chances of success for each of them, but I am not going to do that, mostly because my code would require a significant rework to handle taking the permutation as an input, rather than the number of cards, but also because that wouldn't help us with the 20 card case, and because the curve above is smooth enough that I'm pretty confident the simulations are doing their job.
RSS Feed