Can You Make Something out of Nothing?

You see two functions of zero. I see possibilities.

Welcome to Fiddler on the Proof! The Fiddler is the spiritual successor to FiveThirtyEight’s The Riddler column, which ran for eight years under the stewardship of myself and Ollie Roeder.

Each week, I present mathematical puzzles intended to both challenge and delight you. Beyond these, I also hope to share occasional writings about the broader mathematical and puzzle communities.

Puzzles come out Friday mornings (8 a.m. Eastern time). Most can be solved with careful thought, pencil and paper, and the aid of a calculator. Many include “extra credit,” where the analysis gets particularly hairy or where you might turn to a computer for assistance.

I’ll also give a shoutout to 🎻 one lucky winner 🎻 of the previous week’s puzzle, chosen randomly from among those who submit their solution before 11:59 p.m. the Monday after that puzzle was released. I’ll do my best to read through all the submissions and give additional shoutouts to creative approaches or awesome visualizations, the latter of which could receive 🎬 Best Picture Awards 🎬.

This Week’s Fiddler

From Jeremy Dixon comes a tale of two functions:

Consider f(n) = 2n+1 and g(n) = 4n. It’s possible to produce different whole numbers by applying combinations of f and g to 0. For example, f(0) = 1, f(f(0)) = 3, g(f(0)) = 4, f(f(f(0))) = 7, f(g(f(0))) = 9, f(f(f(f(0)))) = 15, and g(g(f(0))) = 16.

How many whole numbers between 1 and 1,024 (including 1 and 1,024) can you produce by applying some combination of f’s and g’s to the number 0?

Extra Credit

Now consider the functions g(n) = 4n and h(n) = 1−2n. How many integers between -1,024 and 1,024 (including -1,024 and 1,024) can you produce by applying some combination of g’s and h’s to the number 0?

Making the Rounds

There’s so much more puzzling goodness out there, I’d be remiss if I didn’t share some of it here. This week, I’m sharing a challenge posted by Bowen Kerins via the network formerly known as Twitter back in June:

Bill rolls a single six-sided die and continues rolling with the target of rolling a grand total of 7. He succeeds! What is the expected number of Bill’s dice rolls?

Many dice-related puzzles ask you to find the distribution for the sum (or something similar) for a given number of rolls. What I love about this puzzle is how it flips things around in a Bayesian sense, asking you to instead think about the distribution for the number of rolls for a given sum. Great stuff!

Last Week’s Fiddler

Congratulations to the (randomly selected) winner from last week: 🎻 David Cohen 🎻, from Silver Spring, Maryland. I received 98 timely submissions, of which 90 were correct—that was good for a 92 percent solve rate. Way to go, everyone!

Last week’s puzzle was an oldie but a goodie, and came from high school student Meryl Zhang of Plano, Texas—the top math awardee at this year’s Regeneron International Science and Engineering Fair.

In the puzzle, the final 20 players in the Squid Game competition formed a circle and were assigned the whole numbers from 1 to 20, progressing in a clockwise direction. First, contestant 2 was eliminated. Then, the contestant two positions clockwise from where 2 had been (i.e., contestant 4) was eliminated. Next, the contestant two positions clockwise from them (i.e., contestant 6) was eliminated. The counting continued in this manner, wrapping around the circle, which tightened after each elimination. So after contestant 20 was eliminated, the next contestant to go was 3, who at this point was two positions clockwise from where 20 once stood.

You repeated this process until only one contestant remained as the ultimate winner of the game. What was the winner’s number?

Given the small population involved (i.e., 20 contestants), this puzzle was reasonably solved by hand, working through the eliminations one at a time. In the first loop, contestants 2, 4, 6, 8, 10, 12, 14, 16, 18, and 20 were eliminated, leaving contestants 1, 3, 5, 7, 9, 11, 13, 15, 17, and 19 remaining. The next contestant to be eliminated was 3, followed by 7, 11, 15, and 19, leaving 1, 5, 9, 13, and 17 as the survivors. Next, 5 and 13 were eliminated, leaving 1, 9, and 17. After 13’s elimination, 17 was passed over, which meant 1 was the next to go. Then 9 was passed over, which meant 17 was out. Ultimately, the sole survivor was contestant 9.

As I said, this puzzle was an “oldie but a goodie”—solvers including Samee Mushtak and Billy Mullaney recognized that this was a version of the Josephus problem (which, like Squid Game, has a rather morbid backstory). The generalized Josephus problem involves N individuals, with every k^th individual being eliminated. When k is 2, there’s a known formula for the winning number: It’s 2L+1, where L is the difference between N and the greatest power of 2 less than N.

For this specific puzzle, N was 20. The greatest power of 2 less than 20 is 16, which meant L was 4. That meant 2L+1 was equal to 2·4+1, or 9, which was indeed the answer.

Last Week’s Extra Credit

Congratulations to the (randomly selected) winner from last week: 🎻 Rohan Lewis 🎻, from Cary, North Carolina. For the Extra Credit, I received 49 timely submissions, 36 of which were correct—a very respectable 73 percent solve rate.

For extra credit, you ran the Squid Game competition again with the same 20 contestants, but with slightly different rules: Instead of always proceeding two positions clockwise for each elimination, you now proceeded two or three positions clockwise. That is, for each turn, you randomly (and independently of the other turns) picked either two or three positions to move, each with a 50 percent probability. No longer was number 2 guaranteed to be the first contestant eliminated—now numbers 2 and 3 were equally likely to be eliminated first.

Once again, you proceeded clockwise around the circle, tightening it after each contestant was eliminated, until only one contestant remained. This time around, which number was most likely to win the game?

Gone was the deterministic nature of the Josephus problem—in its place was this probabilistic version of the puzzle, which made things a good deal trickier.

Many solvers coded up Monte Carlo simulations, with each step of each simulation randomly moving two or three positions clockwise. After a sufficient number of simulations (say, a few million), you could approximate the probabilities for the different numbers emerging victorious.

Meanwhile, other solvers were able to precisely determine these probabilities. Matt Carlton did this by working backwards. When there were only two competitors remaining, Matt recognized they each had a 50 percent chance of winning. With three competitors remaining (call them A, B, and C, in that order), A had a 50 percent chance of winning, while B and C each had a 25 percent chance. Continuing in this fashion, and with some computer assistance, Matt found that contestant 18 was most likely to win, with a probability of 35,531/2¹⁹, or about 6.7 percent.

I received some beautiful animations that illustrated this result. Solver 🎬 Emilie Mitchell 🎬 succeeded in “shamelessly trying” for a Best Picture Award, showing how the probabilities of remaining in the game changed with each elimination. The final screen of this animation (i.e., the probabilities for each contestant winning) are shown below:

Not to be outdone, 🎬 Tom Keith 🎬 analyzed what happened as the probability of advancing two versus three steps changed. When always advancing two steps per elimination, contestant 9 was guaranteed the victory—that was simply last week’s Fiddler. When always advancing three steps per elimination, contestant 20 was guaranteed the victory. But in between, there was a lot of interesting mathematics happening! (Sure enough, halfway in between, contestant 18 was most likely to win.)

Want to Submit a Puzzle Idea?

Then do it! Your puzzle could be the highlight of everyone’s weekend. If you have a puzzle idea, shoot me an email. I love it when ideas also come with solutions, but that’s not a requirement.