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 Steven Pratt, an autumnal puzzle:
The Major League Baseball playoffs are about to begin. Based on the current playoff format, what is the best possible winning percentage a team can have in the playoffs without winning the World Series? And what is the worst possible winning percentage a team can have in the playoffs and still win the World Series?
Extra credit: How close to these extremes has any actual team come?
Riddler Classic
From Tess Huelskamp, in which you embark on a new career:
You’ve just been hired to work in a juicy middle-management role at Riddler HQ — welcome aboard! We relocated you to a tastefully appointed apartment in Riddler City, five blocks west and 10 blocks south of the office. (The streets of Riddler City, of course, are laid out in a perfect grid.) You walk to work each morning and back home each evening. Restless and inquisitive mathematician that you are, you prefer to walk a different path along the streets each time. How long can you stay in that apartment before you are forced to walk the same path twice? (Assume you don’t take paths that are longer than required, and assume beaucoup bonus points for not using your computer.)
Extra credit: What if you instead took a bigger but more distant apartment, M blocks west and N blocks south of the office?
Solution to last week’s Riddler Express
Congratulations to 👏 Kelci Mumford 👏 of Bainbridge Island, Washington, winner of last week’s Riddler Express!
Last week, Abby and Beatrix were playing a game with two six-sided dice. Rather than having numbers on the sides like normal dice, however, the sides of these dice were either red or blue. In their game, Abby won if the two dice landed with the same color on top. Beatrix won if the colors were not the same. One of the dice had five blue sides and one red side. If the two players had equal chances of winning the game, how many red and blue sides did the other die have?
It had three red sides and three blue sides.
Why? Let’s approach it two ways. First and most simply: If one die has three red sides and three blue sides, it doesn’t matter how many red and blue sides the other die has. The three-red-three-blue die will either match the other die’s color, or not, with equal probability (3/6 = 1/2).
Second, we can explicitly calculate each player’s chances of winning the game. Let X be the number of blue sides on the second die. Abby’s chance of winning (that is, of the colors matching) is:
(5/6)(X/6) + (1/6)((6 – X)/6)
And Beatrix’s chance of winning (that is, of the colors not matching) is:
(5/6)((6 – X)/6) + (1/6)(X/6)
Setting these two chances equal to each other and solving for X gives X = 3.
Solution to last week’s Riddler Classic
Congratulations to 👏 Austin Nar 👏 of Cincinnati, winner of last week’s Riddler Classic!
Last week brought a meta-mathematical challenge. You solved a problem posed by an eccentric billionaire: Namely, you three-colored a map that the billionaire published. The billionaire offered a $10 million prize for the solution, which was awesome, but you couldn’t afford the $10,000 it took to travel to present your solution to her at her distant island lair, which was not awesome. So you headed to the bank to obtain a loan, explaining to the bank manager that you had a solution to an eccentric billionaire’s problem and were due to receive $10 million, so you were a credit risk worth taking. But the manager was skeptical that you solved the problem. You couldn’t just show the manager your solved map, because then he might just kick you out and claim the $10 million for himself. How could you convince the manager that you had solved the problem, securing the $10,000 loan, without giving your actual solution away?
The most beautiful thing about meta-mathematical problems like this is the breadth and depth of ideas that flow my way from all corners of Riddler Nation, many of which were decidedly outside of the box. In fact, this problem may have generated my favorite set of Riddler answers I’ve ever received.
Take solver Dave Moran’s, for a start: Ask the banker for the name of someone he trusts completely. Show the map to that person. Have that person confirm to the banker that the map is properly colored with just three colors. Murder that third person. Use some of the $10 million to hire an excellent criminal defense lawyer. (Dave teaches and practices criminal law, but I imagine that this should not be interpreted as legal advice.)
Solver William Garrard hatched a less bloody plan: Publish your solution on as many platforms as possible, all at once, including your name and face and confirmation of the date and time and so forth. The media would definitely pick this up. [Editor’s note: Can confirm that FiveThirtyEight would pick this up.] If this billionaire really does want to give the prize away, she will catch wind of the news that a solution has been published and then either get you to the lair herself or come to you.
James Tetazoo proposed a solution involving two bitcoins, Jack Townsend suggested using a color-blind go-between, Chris Lanshe suggested an appeal to Grötzsch’s theorem plus a contingent escrow account, Adrian Guilfoyle suggested a jigsaw puzzle,2 Katherine Paur suggested “an electrical circuit based on the dual graph of the map,” others suggested various levels of violence and insult against the poor bank manager, and many others suggested strategies involving attorneys and deferred payment plans. (The trust placed in attorneys here was somewhat troubling.)
But there were also more directly mathematical approaches to getting paid. This puzzle’s submitter, Dan Johnston, suggested the following iterated strategy:
Assume that the map has 100 borders between countries (i.e., pairs of countries that must be different colors). You have your “real solution” that is colored red, blue and yellow. You randomly assign those colors three new colors, instead — say, orange, purple and teal — and color your map with those new colors. Next, you cover up the entire map. You go to the bank manager and ask him to choose two adjacent countries. You then expose those two countries and show him that they are indeed different colors.
But still the banker isn’t satisfied. What if he just guessed a pair of countries that happened to have different colors, even if the map as a whole wasn’t a perfect solution?
Depending on how skeptical your banker is, you’ll be spending a lot of time at the bank. If you were lying about having completed the map, there would be at least one set of adjacent countries that were the same color. In other words, there would have been a 1 percent chance you would have been “caught.” So, after this first reveal, the bank manager should at most be 1 percent confident that you have a real solution.
It’s time to brute-force him into believing you. Repeat the steps you used to make and show the banker the first pair of countries (randomly re-assigning the colors, making a map, covering the map, showing two selected countries) over and over again. If you repeat them 100 times, for example, there is at least a 36 percent chance you could be “fooling” the bank manager with a fake map. If you do it 1,000 times, the likelihood of a lie plummets to a 0.004 percent chance, if you had completed the whole map except for one border. You repeat these steps as many times as needed to satisfy the bank manager.
Finally, and most generally, this problem is tied to the idea of a zero-knowledge proof, of which the method above is one example. It’s a way to prove that you know a thing without giving away any information other than the fact that you know that thing. These types of proofs are really cool and complicated and logical and mathematical and philosophical. Zero-knowledge proofs have applications in encryption, cryptocurrency and the blockchain, ethics, and nuclear disarmament. And, of course, in getting paid by eccentric billionaires.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.