A cool drizzly October day, the kids in school, Brett Kavanaugh ensconced on the Supreme Court: what is a retired guy to do? Those unwilling to let go of a possibly bad habit can read up on Kavanaugh biographical tidbits ancillary to his teen-aged acts of worship at the altar of the American masculinity cult--the mystery, for example, of the source of the dough for his distinctly upscale lifestyle, the seven-figure home in Chevy Chase and private school for the kids and the country club membership and season tickets for the Washington Nationals. His financial disclosure forms do not account for assets or income that might permit all the spending. I, however, am off the case, so that instead I can indulge, with an assist from the FiveThirtyEight Blog, another habit, older and manly, though in a nerdy sort of way. For in addition to the political and athletic number grinding that the site is famous for, there is The Riddler, a series of mathematical puzzles they lob into cyberspace for the entertainment of their dweeby followers, like me. Here's one I worked on this morning between trips to the laundry room:
You go to buy a specific car, whose fair price we'll call N. You have absolutely no idea what N is and the dealer, sadistic capitalist that he is, won't tell you. The dealer enjoys a good chase, though, so without directly revealing the value of N, he takes five index cards and writes down a number on each of them: N, N + 100, N + 200, N + 300 and N + 400. Important: the guy's sadistic but not a math major. The numbers on the cards are numbers, not algebra equations.
He presents the cards to you, one at a time, in random order. (For example, if the price on the second card is $100 more than the first, you can't be sure if those are the two smallest prices, the two largest, or somewhere in between.) Each time he shows you a card, you must either pay the price on that card, or ask to see the next card. You cannot go back to previous cards. If you make it to the fifth and final card, then that is what you must pay. If you play the dealer's game optimally, how much should you expect to pay on average above the fair price N?
The real problem is to discover the optimal strategy, right? If you can figure out what that is, the amount of money above N you'd expect to pay is just arithmetic. I think you can begin to get a handle on the problem by considering a simpler version: suppose the "game" is the same, but there are only three possible prices, $1, $2, and $3. If you played randomly, employing no strategy at all, you'd expect to pay on average $2, since you'd pay each of the three possible prices the same number of times. How to improve on that? Well, if you noodle around just a little bit, it's not that hard to see that you can do better by never paying the price indicated on the first index card. There are only six different orders for the three cards:
$1, $2, $3
$1, $3, $2
$2, $1, $3
$2, $3, $1
$3, $1, $2
$3, $2, $1
I've bolded the price you'd pay if you played according to the following (optimal) strategy: (a) never pay the price indicated on the first drawn card; (b) if the price shown on the second card is lower, pay it; and (3) if the price shown on the second card is higher, pay the price shown on the third card. You can do the arithmetic and satisfy yourself that by this strategy you will pay on average $1.67 instead of $2.00.
Now, bumping up to five possible prices makes the game a lot more complicated. For one thing, while there are only six ways to order three items, there are 120 ways to order five items. It's too cumbersome to list all the possible arrangements of five prices. But, to improve on a random strategy, it's necessary to try to learn something as the game progresses, which means: no matter the number of possible prices, never take the one shown on the first card drawn. If we try to extrapolate the rule for the simple 3-card game, we'd say that in the 5-card game you should take the second card if it's lower than the first. If it's higher than the first, proceed to the third card. But now we have a problem that couldn't arise in the 3-card game. What if the price indicated on the third card is between the ones shown on the first and second? In other words, there are two competing strategies. One would be never to pay the price shown on the first card; instead, as the game progresses, pay the price shown on the first card you reveal that is lower than all the other prices so far revealed. Another would be never to pay the price shown on the first card; instead, as the game progresses, pay the price shown on the first revealed card that is lower than the price shown on the immediately preceding card.
At first, I thought the whole challenge might be to figure out which of these possible strategies was superior. As I was rather tediously trying to work that out, however, it occurred to me that it's somewhat more complicated than that. The more possible prices there are to pay, the more chance you have to put what you learn to good use. For example, suppose that the prices shown on the first two cards are $400 apart. You immediately know that you have revealed the "fair price" and the most marked-up price--the bookends of the range. If the first card showed the fair price, it's--alas!--too late to select it. On the bright side, you know that the second lowest price is out there, and you know what it is. If you don't get it on the third card, proceed until you do get it. Of course, if the second card is $400 less than the first card, you know it's the fair price and you should take it--the three cards you haven't seen are for $100, $200, and $300 over the fair price.
To avoid working with algebraic expressions, let's designate the five possible prices 0 (for "fair price") and 1, 2, 3, and 4 for $100 over, $200 over, $300 over, and $400 over "fair price," respectively. Then, of the 120 possible orders, six begin
0, 4 (in which case we pay 1)
and another six begin
4, 0 (in which case we pay 0).
So we've got the optimal strategy for 12 of the 120 possibilities. What about the rest?
The strategy will be to consider systematically what the possibilities are after the first two cards are revealed. Suppose the second card indicates a price $300 more than the first. That would mean we are dealing either with a sequence beginning 0, 3 or 1, 4. In the first case, 1, 2, and 4 remain. In the second case, 0, 2, and 3 remain. We can't know which case we have, but obviously we should see the third card. To avoid being stuck with either 4 (first scenario) or 3 (second scenario), we should be looking for a card that is 1 higher than the lowest card we've seen, or better. If we are in the first scenario, we will then end up with the 1-card. If we are in the second scenario, we will end up with the 0-card if we are lucky enough to come to it first; otherwise, we'll end up with the 2-card. At this point, we will have considered twelve more of the 120 possible arrangements of cards, and we will have ended up with the 1-card six times, the 0-card three times, and the 2-card three times.
Next up would be the case where the second card is $300 less than the first, and then we'd have to take up in turn the cases where the difference between the first and second cards is only $200 or $100. But this is already getting long, it doesn't get less complicated, and, if you've hung with me this far, you probably want to work it out for yourself anyway. If you do everything the best you can, I think you can expect to pay this salesman, on average, $90 more than the "fair price." Gypped, but quite a bit better than the $200 over fair price you'd expect to pay if you just threw up your arms and chose cards at random.
Comments