Welcome to The Riddler. Every week, I offer up a problem related to the things we hold dear around here — math, logic and probability. These problems, puzzles and riddles come from lots of top-notch puzzle folks around the world, including you, the readers. You’ll find this week’s puzzle below.
Mull it over on your commute, dissect it on your lunch break, and argue about it with your friends and lovers. When you’re ready, submit your answer using the form at the bottom! I’ll reveal the solution next week, and a correct submission (chosen at random) will earn a shoutout in this column. Important small print: If you want to be eligible for the shoutout, I need to receive your correct answer before 11:59 p.m. EST on Sunday — you now have the whole weekend to solve The Riddler!
Before we get to the new puzzle, let’s dwell on last week’s! Congratulations to 👏 Satoru Inoue 👏 of Columbia, South Carolina, our big winner. You can find a solution to the previous Riddler at the bottom of this post.
Now, here’s this week’s Riddler, which comes to us from Mike Donner, an engineer from Virginia Beach, Virginia:
A basketball player is in the gym practicing free throws. He makes his first shot, then misses his second. This player tends to get inside his own head a little bit, so this isn’t good news. Specifically, the probability he hits any subsequent shot is equal to the overall percentage of shots that he’s made thus far. (His neuroses are very exacting.) His coach, who knows his psychological tendency and saw the first two shots, leaves the gym and doesn’t see the next 96 shots. The coach returns, and sees the player make shot No. 99. What is the probability, from the coach’s point of view, that he makes shot No. 100?
[googleapps domain=”docs” dir=”forms/d/1RAMo6opVio5QcA7F4VI-ux6jpqcS75-UwUaElIFT_GE/viewform” query=”embedded=true” width=”760″ height=”960″ /]
And here is the solution to last week’s Riddler, concerning the machinations of a sadistic car dealer. The solution below is adapted from the excellent explanation submitted by our winner, Satoru Inoue. This one was a toughie — only 15.6 percent of submitted solutions were correct, a new record low. And it certainly wasn’t for a lack of trying, as you can see.
If you play the car dealer’s game optimally, you can expect, on average, to pay $90 above the fair price.
To explain why, let’s step back for a second. If you adopted a naive strategy of simply accepting the first card, say, you’d expect to pay $200 over the fair price — simply the average of all the possible markups. That’s our baseline; we can do significantly better. The reason we can do better is that we can learn new information by asking to see additional cards. Put another way: Never pick the first card.
Call the cards — which, remember, display the numbers N, N+100, N+200, N+300 and N+400 — A, B, C, D and E, respectively.
There are two principles at work in determining the optimal strategy.
- If you see two cards that are $400 apart, then you know these are the endpoints, and you can always wait for the lowest card remaining.
- Once you know the optimal strategy with some arbitrary number of cards remaining, you should compare the expected amount you’d pay if you used the optimal strategy to the expected amount you’d pay if you took the card in front of you. In other words, you can determine the strategy recursively, working backwards from the end of the game.
Principle 1 follows from Principle 2, but it simplifies the answer. There are four possible intervals between the first two cards. Here is one strategy that achieves the smallest expected overpayment:
- The first two cards are $400 apart. You now know for sure that you saw A and E. If you saw A then E (which occurs with one out of 20 times), then you can wait for B and pay N+100. If you saw E then A (which also occurs with probability 1/20), then you obviously take A and pay the fair price N.
- The first two cards are $300 apart. These may be A and D, or B and E. The best strategy with the three remaining cards is to wait for the card that is $100 higher than the lower of the first two, or better. If you saw A and D, you are guaranteed to get B. If you saw B and E, you are going to get either A or C with one-half probability (whichever you get first). So the expected amount you pay if you ask to see the third card is N+100. This means that if you saw A, then D or B, then E, you want to see the third card to pay N+100 on average (this occurs one out of 10 times). If you saw D then A, or E then B, you should choose the second card to pay N+50 on average (also one out of 10 times).
- The cards are $200 apart. The best strategy for the three remaining cards (they can be BDE, ACE or ABD) is characterized by the following:
- If you see a card that is lower than the first two, take it.
- If your first four cards are in consecutive order, and the fourth one is the second lowest, take it (e.g. if you saw CADB or DBEC, take the fourth card).
- Otherwise, wait until the end.
This strategy results in you paying on average. This is better than taking the second card even if the second card is 200 lower than the first (the expected amount would be N+100 if you take it). This case occurs three out of 10 times.
- The cards are $100 apart. The strategy for the remaining three cards is:
- If you see a card lower than the first two, take it.
- If you see both A and E, wait until the lowest available.
- Otherwise, wait until the end.
This results in the expected payment of . This is again better than taking the second card. This case occurs four out of 10 times.
The final tally for the overall expected payment is
You pay, on average, $90 more than the fair price, which is not bad at all!
Phew! Other solvers took different tacks, including programmatic solutions. You can find other insightful takes on the solution in these blog posts by readers Jason Shaw, Jon Wiesman and (nom-de-tweet) Honestly Vox. I also recommend this thread on BoardGameGeek, which contains in-depth discussion of the problem.
Finally, intrepid Riddler solver Chris Vandervoort uncovered a pattern beyond the solution to the specific problem posed last week. In fact, he found a generalizable solution for any number of cards the car dealer may present to you. As the number of cards increases from a deck of two (N and N+100), to a deck of five (N, N+100, …, N+400), to an arbitrarily large deck, the expected overpayment increases. But, if you play optimally, you’ll never expect to pay more than $100 over the fair price. The expected overpayment, for decks of increasing size, is shown below.
“I don’t know why,” Vandervoort wrote about the $100 cap in an email. “I guess because math is beautiful sometimes.”