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. If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.
Riddler Express
From Yan Zhang comes a royal murder mystery:
Black Bishop: “Sir, forensic testing indicates the Queen’s assassin, the White Knight between us, has moved exactly eight times since the beginning of the game, which has been played by the legal rules.”
Black King: “So?”
Black Bishop: “Well, to convict this assassin, we need to construct a legal game history. But we just can’t figure out how he got there!”
Can you figure it out?
Riddler Classic
Riddler Nation was deeply saddened to hear of the loss of John Conway last week. It is only fitting that this week’s Classic is a spin on Conway’s Game of Life.
In the most common version of the game, there is an infinite grid of square cells, which are initially either alive or dead. Each square has eight neighbors — the eight squares that surround it. And after every step in time, or “tick,” all the cells are simultaneously updated according to the following rules:
- A living cell with two or three living neighbors remains living.
- A living cell with any other number of living neighbors dies (due to under- or overpopulation).
- A dead cell with exactly three living neighbors comes alive (due to reproduction).
These relatively simple rules lead to some startlingly complex, emergent behaviors. For example, some formations of living cells are known as “oscillators,” which change form from one tick to the next, ultimately returning back to their original formation.
Now suppose we were to replace the infinite grid with a finite grid that has periodic boundary conditions, so that cells in the first row are neighbors with cells in the last row, and cells in the first column are neighbors with cells in the last column. If there are three rows and N columns, what is the smallest value of N that can support an oscillator?
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Rohit S. ÑÑâÐ of Denver, Colorado, winner of last week’s Riddler Express.
Last week, you were seated in an audience, when T-shirts were being launched via cannon in your direction. The rows of seats in the audience were all on the same level, they were numbered 1, 2, 3, etc., and the T-shirts were being launched from directly in front of Row 1.
Additionally, there was no air resistance, and the particular model of T-shirt cannon being used was able to launch T-shirts to the very back of Row 100 in the audience, but no farther.
If the T-shirt was launched at a random angle between zero degrees (straight at the unfortunate person seated in Row 1) and 90 degrees (straight up), which row should you have been sitting in to maximize your chances of nabbing the T-shirt?
While some solvers took an analytical approach, there was no shortage of simulations. For example, if you were to launch a T-shirt at whole number values of degrees between zero and 90, and you recorded which rows they landed in, here’s what you’d find:
Each blue dot represents a T-shirt fired at a different angle, and the red bars show how many T-shirts landed in each row. (Some rows didn’t get any T-shirts because this simulation only used whole number values of the angles.)
Already, it appears that the last few rows received more T-shirts than the others. This result was confirmed by Eli Luberoff, Jason Shaw, Ravi Chandrasekaran and Angelos Tzelepis, the last of whom sampled the angles from zero to 90 degrees at 0.01-degree steps. Every single one of them found that Row 100 had the greatest chance of receiving a T-shirt.
So what’s going on here? As solver J. D. Roaden explained, it helped If we looked at a graph of launch angle θ versus row number R, which physics tells us are related by the equation R = 100·sin(2θ), shown by the blue curve in the graph below:
Meanwhile, the vertical red bar shows the range in angles that will launch a T-shirt to Row 100. Because the blue curve is flattest at the top, that means larger variations in angle have relatively little effect on row number. And so sure enough, Row 100 corresponds to the widest swath of angles. Solver Jonah Majumder specifically found that the chances of nabbing the T-shirt in Row 100 were just over 9 percent. Not bad!
Finally, as an aside, this phenomenon (whereby the maximum possible value is more likely because that’s where it’s changing the least), also explains why rainbows exist. ÑÑÐâ¬Seriously! ÑÑÐâ¬
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Andy Quick ÑÑâÐ of Kitchener, Ontario, Canada, winner of last week’s Riddler Classic.
Last week, you modeled the appearance of spam on the Riddler column. (Scroll down to the comments section — I dare you!)
Over the course of three days, suppose the probability of any spammer making a new comment on this week’s Riddler column over a very short time interval was proportional to the length of that time interval (i.e., the spammers followed a Poisson process).
Also, on average, the column got one brand-new comment of spam per day that was not a reply to any previous comments. Each spam comment or reply also got its own spam reply at an average rate of one per day.
After the three days were up, how many total spam posts (comments plus replies) could I have expected?
So rather than follow your run-of-the-mill Poisson process, these spammers were following what’s known as a nonhomogeneous Poisson process (as nicely illustrated by Josh Silverman), meaning the rate at which spam was being posted changed over time. With every new spam comment, a new stream of potential replies opened up. So while the average rate of comments was initially one per day, the moment a comment appeared the rate jumped to two per day (one for brand-new comments, and one for replies to that first comment). And when a third comment appeared, regardless of whether it was brand new or a reply to a previous comment, the average rate jumped again to three comments per day.
As it turned out, there was a rather direct way to solve for the average number of comments. Solver Austin Shapiro pointed out that the average rate at which new spam appeared was proportional to the number of comments that already existed. (Sadly, to make this math work out just right, that meant that the Riddler column itself had to be counted as spam — it was essentially the very first spam comment to which all others were replying.)
Writing this as a differential equation, if S(t) was the average number of spam comments at time t, then dS/dt = cS, for some constant c. In fact, c was just 1, since the problem stated that the initial rate of spam comments was 1 per day. And so dS/dt = S, which meant S = et. In other words, the spam count was growing exponentially. Yikes!
But let’s return to the original question: How many spam posts could I expect to have after three days? While there would have been e3 total posts, the Riddler column was, of course, never really spam to begin with. Subtracting that off meant there would be e3 − 1, or about 19.1 spam posts on average.
Many solvers went ahead and simulated the scenario, finding similar results. David Robinson coded it up in R, finding that while the average number of spam comments was about 19.1, sometimes it could be much, much larger. Even in just 100 simulations, he found that one resulted in more than 115 spam comments:
Several solvers, like Emma Knight and David Zimmerman, went one step further, finding the precise probability distribution for the number of spam comments over time: The probability of having N comments after t days was e−t·(1 − e−t)N. For any given number of days, this probability distribution was a geometric sequence — so while having zero comments was technically the most likely, the long tail of the distribution meant it was also quite possible to be inundated with spam.
In the end, last week’s column had just four spam comments (some of which have since mysteriously disappeared). I’m thanking my lucky spam filters it wasn’t 115.
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.