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 the next 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.
Due to the holidays, the next column will appear on Jan. 8, 2021. See you in the new year!
Riddler Express
The other day I was playing around in my kitchen with a tall glass and a smaller disk, when, to my surprise, I was able to balance the disk neatly atop the rim of the glass:
First of all, try this at home!
Now suppose you have a disk of radius R and a glass with a circular rim of radius 2R. If you randomly place the disk so that its center lies within the glass’s rim, what is the probability that the disk will balance atop the glass? (Assume the distribution is uniformly spread across the circular area inside the rim.)
Riddler Classic
From Keith Wynroe comes an epic power battle that is sure to wear you down:
The Game of Attrition has two players, each of whom starts with a whole number of “power points.” Players take turns “attacking” each other, which involves subtracting their own number of power points from their opponent’s until one of the players is out of points.
For example, suppose Player A (who goes first) starts with 5 points and Player B starts with 7 points. After A’s first attack, A still has 5 points, while B has been reduced to 2 points (i.e., 7 minus 5). Now it’s B’s turn, who reduces A to 5 minus 2, or 3 points. Finally, on A’s second turn, B is reduced from 2 points to nothing (since 2 minus 3 is −1). Despite starting with fewer points, A wins!
Now suppose A goes first and starts with N points. In terms of N, what is the greatest number of points B can start with so that A will still emerge victorious?
Solution to last week’s Riddler Express
Congratulations to 👏 Andrew Young 👏 of Sarasota, Florida, winner of last week’s Riddler Express.
Tonight is the last night of Hanukkah, which means millions of Jews have been lighting their menorahs over the last eight nights. It is traditional to start with one candle in the rightmost position, which is lit using a central candle called a shamash. On the second night, a second candle is added to the left of the first. On the third night, a third candle is added to the left of the second, and so on, until all eight candles have been added on the final night.
With this system for adding candles, whether you were looking at the menorah from the front (i.e., in your home) or back (i.e., through a window), you could easily determine which of the eight nights of Hanukkah it was by counting the number of candles (other than the shamash). But what if you wanted to make that same menorah capable of tracking more than eight nights?
To do that, you had to devise a new system of adding or moving candles (other than the shamash in the middle, which is always lit) around the menorah so that it could uniquely indicate as many nights as possible. Your system had to read the same forward and backward, so that regardless of whether you were looking at the menorah from the front or the back you’d still know what night it was. What was the greatest number of nights that could be indicated using your system?
Without resorting to methods not stated in the problem (like playing with the heights or colors of the candles), your best bet was to use a binary code. Lit candles represented a one, and unlit positions on the menorah were zeros. With this strategy, the menorah could theoretically indicate up to 256 nights. However, since some of these 256 states read the same forward and backward — an ambiguity that was specifically to be avoided — the answer had to be less than 256.
Realizing that a simple binary code was insufficient, some solvers turned to ternary code. Alex Vornsand took this approach, looking at pairs of candles on either side of the central shamash — either neither candle was lit, one candle was lit, or both candles were lit. With four pairs of candles, this meant there were 34, or 81 distinct states, no two of which read the same forward and backward:
But it was possible to do even better! As solver Francesca Maroney noted, there were 16 symmetric configurations that read the same forward and backward — there were 24 different ways to light the four candles on one side of the shamash, and for each of those there was just one way to light the other four to make the menorah symmetric.
Since 16 of the 256 states were symmetric, that meant the remaining 240 were asymmetric — they read differently forward and backward. These could be paired up as reflections about the shamash, so that you could see either of the two states depending on which side of the menorah you were on. In the end, there were 120 paired states and 16 symmetric states, for a total of 136 distinguishable states — the maximum number of nights your menorah could track.
Sign me up for 136 nights of Hanukkah — and the 136 presents that go with it!
Solution to last week’s Riddler Classic
Congratulations to 👏 Jack Stade 👏 of Lafayette, Colorado, winner of last week’s Riddler Classic.
Last week, the Potentate of Puzzles challenged five lucky citizens with a test. The potentate had countless red hats, green hats and blue hats. She said to the citizens, “Tomorrow, you will all be blindfolded as I place one of these hats on each of your heads. Once all the hats are placed, your blindfolds will be removed. At this point, there will be no communication between any of you! As soon as I give a signal, everyone must guess — at the same time — the color of the hat atop their own head. To win this challenge, at least one of you must guess correctly!”
The potentate continued: “The good news is that there’s a little more information you’ll have. I will be arranging you into two rows, with two of you in one row and three of you in the other. Citizens in the same row cannot see each other, but they can see all the citizens in the other row. Finally, each citizen will know their placement within their own row — that is, whether they are seated on the left or right or in the middle.”
What strategy could the citizens have devised beforehand so that at least one of them guessed correctly?
At first blush, this seemed hopeless. With five hats, each of which could be three colors, there were a total of 35, or 243, cases to consider. How could the five citizens possibly cobble together enough information to ensure that at least one of them guessed correctly?
Virtually all solvers treated this as the logic problem it was intended to be, experimenting with different rules for the citizens. But before proceeding down this road, I want to give a tip of the hat (see what I did there?) to the creative approach of solver Josh Silverman, who used a genetic algorithm to computationally find a solution. But enough with the computers!
The puzzle’s submitter, Alex van den Brandhof, originally penned this puzzle with fellow Dutchman Dion Gijswijt for Pythagoras, a Dutch magazine for high school math students. One solution, courtesy of Alex, is as follows:
First, let’s slap some labels on the positions and the hat colors. Let’s call the citizens in the row of two A and B, and the citizens in the row of three C, D and E. Let’s also convert those colors into numbers — a red hat has a value of 0, a green hat has a value of 1 and a blue hat has a value of 2. We then call the values (again, representing the colors) of the respective positions a, b, c, d and e.
First off, C guessed a (the color of A’s hat), and D guessed b (the color of B’s hat). Meanwhile, E guessed the sum of a and b, modulo 3. For example, if A and B both had blue hats — each with a value of 2, according to the aforementioned scheme — then E would have guessed green (which has a value of 1), since 2 + 2 equals 4, which is congruent to 1 (mod 3).
Should any one of those three (C, D and E) have guessed their own hat color correctly, then the citizens would be victorious. Therefore, when A and B made their guesses, they might as well have assumed that C, D and E were all wrong. That meant A shouldn’t have guessed c, because if A and C had the same color hat, then C would already have been correct. Similarly, B shouldn’t have guessed d, because if B and D had the same color hat, then D would already have been correct. And finally, both A and B should have assumed that the sum of their hat values (mod 3) was different from E’s guess — otherwise E would have been correct.
At this point, no matter what colors A and B saw on the hats of C, D and E, it was always possible for at least one of them to be correct — in the event that C, D and E were all wrong.
For example, suppose the color values are as follows: a = 0, b = 2, c = 2, d = 1 and e = 1. Here’s how this scenario would play out for C, D and E:
- Seeing that a = 0, C guesses 0 — incorrectly.
- Seeing that b = 2, D guesses 2 — incorrectly.
- Seeing that a = 0 and b = 2, E guesses 0 + 2 (mod 3), or 2 — incorrectly.
With three incorrect guesses, the pressure is then on A and B. Looking at the hats of C, D and E, A and B both know that A shouldn’t guess 2, B shouldn’t guess 1, and that the sum of their guesses (mod 3) shouldn’t be 1. That left just three possible cases to consider:
- A guesses 0 and B guesses 0, for a sum of 0.
- A guesses 0 and B guesses 2, for a sum of 2.
- A guesses 1 and B guesses 2, for a sum of 0.
If A guesses 0 and B guesses 2, at least one of them is guaranteed to be correct! This sort of result played out for all 243 combinations of a, b, c, d and e — it was always possible for at least one citizen to guess correctly.
Next time, the potentate will be sure to make use of her countless yellow hats as well, in which case it will surely take more than five citizens working together to complete the challenge …
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