Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. Two puzzles are presented each week: the Riddler Express for those of you who want something bite-size and the 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. Please wait until Monday to publicly share your answers! If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.
Riddler Express
Last weekend’s New York City Marathon was canceled. But runners from Des Linden — one of the top American marathoners — to FiveThirtyEight’s own Santul Nerkar — my number one editor — still went out there and braved the course. Santul finished in a time of 3:41:43 (3 hours, 41 minutes, 43 seconds), which averaged to 8 minutes, 27 seconds per mile.
Suppose, while training, Santul completed two 20-mile runs on a treadmill. For the first run, he set the treadmill to a constant speed so that he ran every mile in 9 minutes.
The second run was a little different. He started at a 10 minute-per-mile pace and accelerated continuously until he was running at an 8-minute-per mile pace at the end. Moreover, Santul’s minutes-per-mile pace (i.e., not his speed) changed linearly over time. So a quarter of the way through the duration (in time, not distance) of the run, his pace was 9 minutes, 30 seconds per mile, halfway through it was 9 minutes per mile, etc.
Which training run was faster (i.e., took less time) overall? And what were Santul’s times for the two runs?
Riddler Classic
Mathematician John von Neumann is credited with figuring out how to take a biased coin (whose probability of coming up heads is p, not necessarily equal to 0.5) and “simulate” a fair coin. Simply flip the coin twice. If it comes up heads both times or tails both times, then flip it twice again. Eventually, you’ll get two different flips — either a heads and then a tails, or a tails and then a heads, with each of these two cases equally likely. Once you get two different flips, you can call the second of those flips the outcome of your “simulation.”
For any value of p between zero and one, this procedure will always return heads half the time and tails half the time. This is pretty remarkable! But there’s a downside to von Neumann’s approach — you don’t know how long (i.e., how many flips) the simulation will last.
Suppose I want to simulate a fair coin in at most three flips. For which values of p is this possible?
Extra credit: Suppose I want to simulate a fair coin in at most N flips. For how many values of p is this possible?
Solution to last week’s Riddler Express
Congratulations to 👏 Nilesh Shah 👏 of Seattle, Washington, winner of last week’s Riddler Express.
Last week, while waiting in line to vote early, I overheard a discussion between election officials. Apparently, there was a political sign within 100 feet of the polling place, against New York State law.
This got me thinking. Suppose a polling site was a square building whose sides were 100 feet in length. An election official took a string that was also 100 feet long and tied one end to a door located in the middle of one of the building’s sides. She then held the other end of the string in her hand.
What was the area of the region outside of the building she could reach while holding the string?
Had there been no building, but if she were still constrained to be within 100 feet of a fixed point, then the region she could have reached was anywhere within a 100-foot circle, whose area was 𝜋(100)2, or about 31,416 square feet. Due to the building, that area served as an upper bound, meaning the answer had to be less than that.
At this point, there were two approaches. A few readers subtracted the overlapping area between the building and the 100-foot circle. The geometry here was a little involved, but it yielded an answer of (5𝜋/6−√3/4)·1002, or about 21,849 square feet. However, this wasn’t quite right either.
Why was that? Because this assumed that the string was able to pass through the building. While it was Halloween last week, that sort of “ghostly” string behavior would simply have been too paranormal. So whenever the election official lost line of sight with the door where the string was tied, 50 feet of string were taut against the wall of the building, leaving her with a 50-foot radius with which to move around.
Solver Tamera Lanham sketched out the accessible area:
The red region on the right was a semicircle with a radius of 100 feet, meaning its area was 𝜋(100)2/2, or about 15,708 square feet. Meanwhile, the two blue regions were both quarter-circles with a radius of 50 feet. Together, these quarter-circles formed a semicircle whose area was 𝜋(50)2/2, or about 3,927 square feet.
All together, the area of the region the election official could reach was 6,250𝜋, or about 19,635 square feet.
This riddle was a version of what are known as goat problems, in which a goat is tethered to part of a fence and you are tasked with calculating its grazing area. If you thought the square shape of the building wasn’t challenging enough, try re-running the problem for a circular building. It’s tricky!
Solution to last week’s Riddler Classic
Congratulations to 👏 Brian Corrigan 👏 of Los Angeles, California, winner of last week’s Riddler Classic.
Last week, you and 60 of your closest friends decided to play a socially distanced game of hot pumpkin.
Before the game started, you all sat in a circle and agreed on a positive integer N. Once the number had been chosen, you (the leader of the group) started the game by counting “1” and passing the pumpkin to the person sitting directly to your left. She then declared “2” and passed the pumpkin one space to her left. This continued with each player saying the next number in the sequence, wrapping around the circle as many times as necessary, until the group had collectively counted up to N. At that point, the player who counted “N” was eliminated, and the player directly to his or her left started the next round, again proceeding to the same value of N. The game continued until just one player remained, who was declared the victor.
In the game’s first round, the player 18 spaces to your left was the first to be eliminated. Ricky, the next player in the sequence, began the next round. The second round saw the elimination of the player 31 spaces to Ricky’s left. Zach began the third round, only to find himself eliminated in a cruel twist of fate. (Woe is Zach.)
What was the smallest value of N the group could have used for this game?
A good first step was to nail down the important information from the problem. In the first round, when there were 61 players, the pumpkin went around the circle some number of times (it could have been zero times, once, twice, etc.) and then 18 more spaces. In other words, N had to be some multiple of 61 (one multiple for each time the pumpkin went around the circle) plus 19. In modular arithmetic notation, this meant that N ≡ 19 (mod 61).
Why did you have to add 19, and not 18? Because after the pumpkin had finished going around the circle, you and the 18 people to the left of you all counted off. And you plus the 18 others made 19 people in total.
In the second round, when there were 60 players, the pumpkin again went around some number of times and then 31 more spaces. That told you that N ≡ 32 (mod 60). And in the third round, when poor Zach took himself out of the competition, you learned that N was 1 more than a multiple of 59, i.e., N ≡ 1 (mod 59).
Because the numbers 59, 60 and 61 were all relatively prime, the Chinese remainder theorem told you that there was a single value of N between 1 and 59·60·61, or 215,940, that satisfied all three of the aforementioned modular relations. But while it was one thing to prove there was a solution, finding it was another matter entirely.
One way to do this was through brute force coding — searching for the one number less than 215,940 that had a remainder of 19 when divided by 61, 32 when divided by 60 and 1 when divided by 59. That smallest number was 136,232. Thanks to the wonders of modular arithmetic, any multiple of 215,940 plus 136,232 would also have resulted in the same sequence of eliminations.
For extra credit, you had to play this game to its conclusion, where you were identified as Player No. 1, the player to your left as Player No. 2 and so on. Once again, your computer was your friend. If you simulated the rest of the game, it was Player No. 58 who emerged as the winner.
And for extra extra credit, you had to find the smallest value of N for which you, Player No. 1, won the game. This question was ambiguous as to whether you simply wanted the smallest value of N or the smallest value of N that also resulted in the eliminations listed in the original problem. The answer to the former was 140, while the answer to the latter was a whopping 42,892,352. Only five solvers found this latter result: Angela Zhou, Peter from Hanover, Germany, Emma Knight, Jim Waters and Asha O’Shaughnessy. They will each be winning an imaginary hot pumpkin!
Finally, hats off to those who attempted this not with code, but by hand or with spreadsheets. One such solver, Shane Tilton, said he was content with simply having been invited to play a game of hot pumpkin in the first place.
Who needs to play a game that requires 42 million turns to win when, more importantly, you have 60 good friends to play it with?
Want more riddles?
Well, aren’t you lucky? There’s a whole book full of the best puzzles from this column and some never-before-seen head-scratchers. It’s called “The Riddler,” and it’s in stores now!
Want to submit a riddle?
Email Zach Wissner-Gross at riddlercolumn@gmail.com