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
Chess fans like to crow that there are more possible games of chess than there are atoms in the universe. Well la di da. What about us tic-tac-toe devotees? How many possible games of tic-tac-toe are there for us?
Riddler Classic
From Tom Hanrahan, a twist on the classic:
You are about to play a game of tic-tac-toe, with one advantage and one big disadvantage. The advantage is you get to go first. The disadvantage is you are blindfolded and therefore not informed of your opponent’s moves.
It works as follows. The squares of the board are numbered 1 through 9, like so:
\begin{matrix}\nonumber 1&2&3\\4& 5 &6\\7 &8& 9\end{matrix}
You go first, calling out a number corresponding to the square in which you would like your “X” to be placed. Your opponent then chooses a square for her “O,” but you don’t know which. You continue like this, alternating turns. Whenever you choose a square that is already occupied by your opponent, you are informed that the square is occupied, and you must then choose another one until you find an empty square.
Can you devise a strategy where (just like in regular tic-tac-toe!) you are guaranteed never to lose?
Solution to the previous Riddler Express
Congratulations to 👏 Harry Posner 👏 of Boston, winner of last week’s Riddler Express!
Last week we met Louie, who lived in a town that had a 50 percent chance of rain each morning and an independent 40 percent chance each evening. Louie walked to and from work each day, bringing an umbrella with him if it was raining and not bringing one if it wasn’t. On Sunday night, two of his three umbrellas were with him at home and one was at his office. What were the chances that he made it through the work week without getting wet?
The chances of Louie staying nice and dry were exactly 69.27 percent.
This puzzle’s submitter, Josh Vandenham, suggested three ways to get to the answer. The first is to proceed by brute force through all of the possible weather patterns, keeping track of Louie’s umbrellas in each case. There are two relevant times of day, for five days, and two things can happen at each of those points (rain or shine), therefore there are \(2^{10}=1,024\) possible weather patterns. That’s a lot, sure, but not totally impossible.
The second is to pare down the possibilities and just keep track of the different “states” of Louie’s umbrellas. He could have three at home and zero at work, two at home and one at work, one at home and two at work, or zero at home and three at work. Just four states, which isn’t too complicated. We can see the probability of each state in this glimpse of the spreadsheet of solver Nate Langhinrichs.
By the the time Louie arrives home on Friday night, there is a 30.73 percent chance he has gotten caught out in the rain, sans umbrella, or a 69.27 percent he’s stayed dry.
The third way to solve is to generate some computer-simulated meteorology and commutes. Solver Lowell Vaughn, for example, took this approach and was kind enough to share his Python code.
Finally, yet another way to approach this problem would be with something called Markov chains — models of random events, which use some fancy linear algebra stuff like matrices. In this approach, the state of affairs (the umbrellas) depends on the state of affairs that came before. This approach was used to great effect by solver Aaron Cote. The movement through the random states (the work week) is described by a transition matrix, which contains the probabilities of umbrellas moving from one place to another on any given day. In our particular case, the matrix looks like this:
\begin{pmatrix}\nonumber 0.3 &0.2 &0.0 &0.0 &0.5\\
0.3 &0.5 &0.2 &0.0& 0.0\\
0.0 &0.3 &0.5 &0.2& 0.0\\
0.0 &0.0 &0.3 &0.5 &0.2\\
0.0 &0.0 &0.0 &0.0 &1.0\end{pmatrix}
In this solution, there are five states: zero, one, two or three umbrellas at home plus the state in which Louie has already gotten wet. The rows of the matrix are Louie’s current state, and the columns are his destination. For example, he starts in the third row (two umbrellas at home). There is no chance he’ll end up with zero umbrellas at home, there’s a 0.3 chance he’ll end the day with just one at home, a 0.5 chance with two at home, a 0.2 chance with three at home, and no chance he’ll get wet on this first day. To get the probabilities for the entire work week, we simply multiply this matrix by itself five times, representing the meteorological randomness unfolding over the five days, which gives us the following:
\begin{pmatrix}\nonumber 0.04791 &0.07634 &0.04976 &0.01776 &0.80823\\
0.11451 &0.19889 &0.15274 &0.06752 &0.46634\\
0.11196 &0.22911 &0.22553 &0.12610 &0.3073\\
0.05994 &0.15192 &0.18915 &0.12425 &0.47474\\
0 &0 &0 &0 &1\end{pmatrix}
Last, we take a look at the third row (the state in which he began) and the final column: That’s the chance he gets wet during the week. Subtract from 1 to find the chance that he didn’t get wet and you get 69.27 percent.
All in all, given the extremely precipitous climate in which Louie lives, his haphazard umbrella scheme doesn’t work too badly. TGIF.
Solution to the previous Riddler Classic
Congratulations to 👏 Steve Altschuld 👏 of New Albany, Ohio, winner of last week’s Riddler Classic!
Last week, seven antisocial settlers were moving to a circular prairie with a radius of 1 mile, where they would temporarily overcome their anxieties to work together to build houses that were far apart from each other. Specifically, they wanted to maximize the average distance between each settler and his or her nearest neighbor. With seven houses to build, this was pretty straightforward: One would build his house in the center of the circle, while the other six would form a regular hexagon along its circumference. Every settler would be exactly 1 mile from his nearest neighbor, so the average distance is 1 mile. But at the last minute, one especially antisocial settler canceled his move to the prairie altogether, leaving just six settlers with houses to build. With fewer people, could they find a better arrangement? Could they increase the average distance to more than 1 mile?
Yes, indeed they could. Specifically, they could increase the average nearest-neighbor distance to about a whopping 1.0023 miles! Ah, wide-open spaces.
Here’s what the optimal antisocial prairie neighborhood looks like, courtesy of this puzzle’s submitters, Randi Goldman and Zach Wissner-Gross.
Notice that the “center” house is just a little bit off-center. That’s the key.
The particular case of six settlers turns out to be an unusually tricky one, as Randi and Zach explained: If there are two settlers, they’ll simply build houses at diametrically opposite points on the circumference. If there are three, four or five settlers, they will arrange their houses as a regular polygon. If there are seven settlers, they’ll form a regular hexagon plus one settler in the center of the circle. But six is different.
Our winner this week, Steve, explained how he got started with his solving: With six settlers, you can place five houses on the circle and one in the middle. (If all six are on the circle, the best you can do is 1 mile apart.) I placed the five outer houses where they would go if I were creating a hexagon without the bottom vertex. I then realized that I could move the center house north and south a bit and slide two pairs of houses — the two pairs opposite each other east-west on the circumference, one pair above the other pair — around the edge of the circle a bit, in tandem. So now I have a formula with three variables: the distance from the center house to the top house, the angle of the top pair from the top vertex, and the angle of the bottom pair from top vertex. This would be a fairly horrendous equation, so I did what many of us do: I spreadsheeted it and toggled until I got my answer.
Solver Laurent Lessard presented his “modeling and optimization” approach, in which he considers various methods for solving such optimization problems, including hill-climbing, interior points, simulated annealing and the very cool-sounding particle swarms. He illustrated the optimal arrangements for this problem not only for six settlers but also for all numbers from two to 21 — from the simple east-west separation all the way to the intricate Ritz cracker.
This excellent solution sparked an interesting discussion on Twitter, in which mathematical collaborations were proposed, additional optimization techniques were suggested, and it was pointed out that a whole field of academic research was devoted to questions like this as they relate to electron crystals. Not only that, I was alerted to what has become my new favorite website: packomania.com. It is what you think it is.
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! Consider your holiday shopping done.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.