Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. There are two types: Riddler Express for those of you who want something bite-size and Riddler Classic for those of you in the slow-puzzle movement. Submit a correct answer for either,1 and you may get a shoutout in next week’s column. If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.
Riddler Express
From Andrew Simmons, a puzzle of colorful architecture:
You must build a very specific tower out of four differently colored pieces that can be stacked in any order. But when you start building, you don’t know what the correct order is. Upon assembling the pieces in some order, you can consult an architectural oracle (he goes by Frank) who will inform you if zero, one, two or all four pieces of the tower are in the correct position. Your tower doesn’t count as finished until the oracle confirms your solution is correct. How many times should you have to consult the oracle, in the worst case,2 to assemble the tower correctly?
Riddler Classic
From Joshua Herbison, a classic puzzle of logical jailbreak:
One hundred prisoners are put into 100 completely isolated cells, numbered 1 to 100. Once they are in their cells, they cannot communicate with each other in any way. They are taken by the warden one at a time, but in no particular order, to a special room, Cell 0, in which there are two levers. As the prisoners enter the room, each lever is either up or down, but the levers’ starting positions are unknown. When in the room, a prisoner must flip exactly one of the levers. At any point, any prisoner may declare to the warden that all of the prisoners have been to the room. (The warden will take prisoners to the room indefinitely until someone makes a guess.) If the prisoner is correct, they are all released. If not, they are all executed.
Knowing these rules, what strategy can the prisoners devise beforehand that will guarantee their release? How many trips to Cell 0 will it take on average before they are released?
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Carolyn Homer ÑÑâÐ of Alexandria, Virginia, winner of last week’s Express puzzle!
What’s the maximum amount of money that can possibly be won by one contestant in a single game of “Jeopardy!”?
It’s $566,400.
The key to the solution is figuring out where and when the Daily Doubles need to pop up to maximize your winnings. You want to hit the Daily Doubles at the very end of each round, and you want them to be hiding behind the lowest dollar amounts on the board, so as not to take away from the money you can win otherwise. (A Daily Double on a $1,000 slot means you can’t win that $1,000.)
In the first round, the five dollar amounts range from $200 to $1,000 across six categories. So to maximize your winnings, you get all the questions right except for a single $200 question at the end which, lucky you, happens to be the Daily Double. You wager it all on that Daily Double (go for the glory!), and answer correctly. So, in the first round, you can win:
[6×($200 + $400 + $600 + $800 + $1,000) – 200]×2 = $35,600
In the second round, the dollar amounts range from $400 to $2,000. This time, there are two Daily Doubles, which we’ll place on two of the $400 squares and uncover last, which means we can double our total twice. So at the end of the second round, we can bank:
[$35,600 + 6×($400 + $800 + $1,200 + $1,600 + $2,000) – 400 – 400]×2×2 = $283,200
In Final Jeopardy, we can double that total:
$283,200×2 = $566,400
Not bad for a half-hour’s work!
Now, some hardcore “Jeopardy!” fans among you may protest this result, arguing that Daily Doubles never appear behind the lowest dollar amounts on the board. And while it’s true that it’s very rare, it’s not unheard of. In 2015, Flowing Data’s Nathan Yau examined 13,663 actual Daily Doubles and found that they do, in fact, sometimes pop up on the top row.
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Phillip Bradbury ÑÑâÐ of Gosford, Australia, winner of last week’s Classic puzzle!
Last week, we introduced Coinball, a contest where two players take turns trying to call a fair coin toss. The game lasts for 100 total tosses, 50 tosses for each player. On each toss, the player calling it announces either “heads” or “tails” and either “rush” or “pass.” If he says “rush,” he gets one point if he calls the toss correctly, and his opponent gets one point if the call is incorrect. Saying “pass” means the toss is worth two points to the caller if he calls the toss correctly and two points to his opponent if he does not. The player with the most points wins.
We asked three questions about this game: If you know your opponent always calls “rush” and you follow the optimal strategy given that knowledge, what are your chances of winning? What if you know your opponent always calls “pass”? And if you and your opponent both play optimally, is it better to go first or second?
Here’s the optimal way to play against another smart opponent, in short: If you’re ahead, rush. If you’re behind, pass. As Coinball’s inventor, Guy Moore, explained, you do this “to minimize fluctuations when you are in the lead and maximize them when you are behind.” It’s a result that my colleague Ben Morris, who loves his NFL gunslingers, would be proud of.
(What you do when you’re tied varies a bit depending on if you go first or second. If you go first, mix it up when it’s tied and pass in odd rounds and rush in even rounds. If you go second, rush if you’re tied.)
Given the length of the game, the win probabilities are probably best left to your computer. The general approach you can use is to start at the end of the game and work backward to the beginning, using something called a recurrence relation. Solvers Phillip Bradbury, Calvin Deng and Hector Pefo were kind enough to share the code they used to get the solutions. And Tom Snively created an interactive coinball simulator to put strategic ideas to the empirical test.
Here’s how all the probabilities shake out in the end: If your opponent always calls “rush” and you play optimally, you win about 60 percent of the time. If your opponent always calls “pass” and you play optimally, you win about 56 percent of the time. Naturally, your chances in both of these cases are better than 50 percent since you can vary your strategy while your opponent cannot. If you both play optimally, the player going first wins about 49 percent of the time. The player going second, and therefore last, wins about 51 percent of the time. When you go last, you’re able to make the correct decision in each round because you have all the information.
Karl Leswing turned this game into modern art, plotting the optimal choice for a player who goes first over the rounds of the game (x-axis) and the difference in score (y-axis) — tied games are in the middle of the axis, on the line labeled 10. Purple means you should pass, white means you should run, and pink means it doesn’t make any difference.
Hang it in the Louvre.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.
CLARIFICATION (Oct. 20, 2017, 10:30 a.m.): A previous version of the Riddler Classic left out some information. Prisoners entering Cell 0 must flip a lever. The story has been updated.