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
Yesterday was the first night of Hanukkah, which means millions of Jews began lighting their menorahs. 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 are looking at the menorah from the front (i.e., in your home) or back (i.e., through a window), you can easily determine which of the eight nights of Hanukkah it is 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’d have 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 can uniquely indicate as many nights as possible. Your system must read the same forward and backward, so that regardless of whether you’re looking at the menorah from the front or the back you will still know what night it is. What is the greatest number of nights that could be indicated using your system?
The solution to this Riddler Express can be found in the following column.
Riddler Classic
From Alex van den Brandhof comes a matter of life and death:
The Potentate of Puzzles decides to give five unlucky citizens a test. The potentate has countless red hats, green hats and blue hats. She says 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. If at least one of you guesses correctly, all of you will survive! Otherwise …”
The potentate continues: “The good news is that there’s a little more information you’ll have. I will be arranging you into two rows facing each other, 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.”
Can the citizens devise a strategy beforehand that ensures their survival? If so, what is the strategy?
The solution to this Riddler Classic can be found in the following column.
Solution to last week’s Riddler Express
Congratulations to 👏 Helen Jannke 👏 of Acton, Massachusetts, winner of last week’s Riddler Express.
Last week, a family of five had a book exchange for Christmas. First, each person put their name in a hat. The hat was shaken, and then each person drew a name from the hat and gave that person a book. However, if anyone drew their own name, they all put their names back into the hat and started over.
What is the probability that no one drew their own name?
There were five possible names the first person could have drawn, four names the second person could draw, three for the third, two for the fourth and just one for the fifth. That meant the total number of scenarios to consider here was 5·4·3·2·1 — that is, 5!, or 120. For many solvers, this number was small enough that it was possible to list out all 120 possibilities and count up how many of them resulted in no one drawing their own name.
But with some clever counting, you could add up these cases more efficiently. One way to do this was to represent the five people as five points on a directed graph. Then, if person A drew the name of person B, you drew a line from point A to point B on the graph. After you drew all five lines (one for each drawing), there were three possibilities:
- The lines formed one big cycle, looping around all five points before returning to the start.
- The lines formed two cycles, one with three points and another with two points.
- One of the lines connected a point to itself.
It was that third case — when a line connected a point to itself — that was problematic. It meant that someone had drawn their own name from the hat. Fortunately, counting up the first two cases was manageable.
To make one big cycle, you could pick any point to start with. There were four remaining points to which you could draw a line. From that selected point, there were three points to visit next — then two, and then one, before returning back to your starting point. All told, that accounted for 4!, or 24, unique cycles.
Counting up the graphs with two cycles (one with three points and the other with two) was a little trickier. First you had to choose which two points belonged in the cycle of two, while the remaining three points were then relegated to the cycle of three. There were 5 choose 2, or 10, ways to do this. Then, for each of these 10 ways, there was just one way to link up two points to make a cycle (each point went to the other), but two ways to link up three points (i.e., they could loop clockwise or counterclockwise). That made for 20 graphs with two cycles.
And so, among the 120 possible graphs, 44 of them (24 + 20) had no points connected to themselves. That meant the probability that no one picked their own name was 44/120, or 11/30, or about 0.37. On average, it would take the family of five about three drawings to get a successful one in which no one chose their own name.
This problem was equivalent to finding the probability that a random permutation of five people was also a derangement, meaning no one wound up in their own starting position. The number of derangements for N objects is commonly written as !N. That meant the probability that no one picked their own name from a family of N could be written as !N/N! — a delightful notational palindrome.
As the number of family members continued to increase, !N/N! approached a rather remarkable value, for which 11/30 (this week’s answer) was a decent approximation. To learn more, I recommend David Ding’s writeup of this puzzle.
Solution to last week’s Riddler Classic
Congratulations to 👏 Angela Zhou 👏 of New York City, winner of last week’s Riddler Classic.
Last week, three friends were baking holiday cookies together. They had a flat layer of cookie dough in the shape of an isosceles right triangle (shown below). They wanted to design a cookie cutter that would cut out three identical (i.e., congruent) cookies. The cookies had to be as large as possible while staying within the triangle and without overlapping each other.
Had there been two friends or four friends, they could have used all the cookie dough, but with three friends, some dough went to waste.
What was the greatest percentage of cookie dough that could be used up by the three identical cookies?
This was a delicious challenge. Full disclosure: According to the puzzle’s submitter, Dean Ballard, this puzzle was proposed by Karl Scherer of Auckland, New Zealand, in the 2002-03 volume of the Journal of Recreational Mathematics. Along with the problem, Sherer submitted a solution that used exactly 90 percent of the cookie dough. Two issues later, Dean had his own solution published, which we’ll return to in just a moment.
For now, here are a few of the top submissions from the past week:
Bram Carlson used approximately 86.6 percent of the cookie dough with a cyclic quadrilateral cookie cutter:
Ignas from London, England, used approximately 90.3 percent of the cookie dough with a a truncated parallelogram cutter:
Meanwhile, Thomas Stone did a shade better than Ignas, using approximately 91.3 percent of the cookie dough with a funky-looking hexagonal cookie cutter:
Angela Zhou, this week’s winner, used approximately 94.1 percent of the cookie dough with a trapezoidal cookie cutter. This was exactly the same result that Dean achieved almost 20 years ago.
But the story didn’t end there. According to Dean, in the very same issue in which his solution appeared, an even better solution had been identified by Robert Wainwright and Richard Hess, which used up almost 95.5 percent of the cookie dough:
Dean and I believe this remains an open problem. If you can do even better than 95.5 percent, let us know!
For extra credit, you had to make three identical cookies from a sphinx of cookie dough. Keen-eyed solvers noted that there was no restriction on the convexity of the cookie cutter. That made it possible to get arbitrarily close to using 100 percent of the cookie dough.
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