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 or send me an email.
You are driving from Riddler City to Puzzletown, which are separated by 1,500 miles of highway. On a full charge, your electric car can drive for 500 miles before it needs a recharge. Fortunately, the highway has charging stations every 250 miles, with the first in Riddler City and the last in Puzzletown.
Once you commit to charging your car at a station, you must wait until it is fully charged. For the purposes of this riddle, put aside anything you know about electronics and assume that the charging occurs at a constant rate. Also, assume that you can comfortably roll into a charging station just as your car runs out of power and recharge it there.
You begin your journey with a full charge. Before heading out, you want to come up with an itinerary for which charging stations you’ll stop at along the way. Being impatient, you also want to arrive in Puzzletown as quickly as possible, meaning you want to minimize the time spent waiting at charging stations.
How many distinct itineraries are possible?
From Michael Branicky comes a word puzzle that is the G.O.A.T.:
In the game of Anigrams, you unscramble successively larger, nested collections of letters to create a valid “chain” of six English words between four and nine letters in length.
For example, a chain of five words (sadly, less than the six needed for a valid game of Anigrams) can be constructed using the following sequence, with each term after the first including one additional letter than the previous term:
- DEIR (which unscrambles to make the words DIRE, IRED or RIDE)
- DEIRD (DRIED or REDID)
- DEIRDL (DIRLED, DREIDL or RIDDLE)
- DEIRDLR (RIDDLER)
- DEIRDLRS (RIDDLERS)
What is the longest chain of such nested anagrams you can create, starting with four letters?
Extra credit: How many possible games of Anigrams are there? That is, how many valid sets are there of four initial letters, and then five more letters added one at a time in an ordered sequence, that result in a sequence of valid anagrams? (Note: Swapping the order of the first four letters does not result in a distinct game.)
Solution to last week’s Riddler Express
Congratulations to 👏 Derek Kaplan 👏 of Hollidaysburg, Pennsylvania, winner of last week’s Riddler Express.
In this year’s Battle for Riddler Nation, you had to assign 100 phalanxes of soldiers to 10 castles, each worth a distinct number of points. For example, you could assign all 100 phalanxes to a single castle (and none to the others), split them evenly so that there were 10 phalanxes at every castle or arrange them in some other way.
What was the total possible number of strategies you could have submitted?
This is a classic problem in combinatorics. To figure out the total number of strategies, solver Adrian Rodriguez imagined lining up the 100 phalanxes in a row. Somewhere in that very same row, you also have nine (i.e., one less than 10) dividers. Suppose that all the phalanxes before the first divider are assigned to Castle 1, all the phalanxes between the first and second dividers are assigned to Castle 2 and so on. Finally, all the phalanxes after the ninth divider are assigned to Castle 10. Note that this makes it possible for some castles to have no corresponding phalanxes if two dividers are consecutive or if a divider comes before or after all the phalanxes.
The key insight here is that every ordering of phalanxes and dividers corresponds to exactly one strategy for assigning them to castles, and vice versa. So how many ways were there to order 100 phalanxes and nine dividers? Since the phalanxes were indistinguishable from each other, as were the dividers, the number of orderings was 109 choose 9. In other words, among the 109 items (phalanxes or dividers) in the row, you had to choose the nine positions where the dividers went. (Alternatively, you could have chosen the 100 positions where the phalanxes went, which gave you an equivalent result since 109 choose 9 and 109 choose 100 were equal.)
In the end, 109 choose 9 was equal to 109!/(100!·9!), or 4,263,421,511,271. In a battle of these more than four trillion strategies, I wonder which strategy would come out on top.
Solution to last week’s Riddler Classic
Congratulations to 👏 Izumihara Ryoma 👏 of Toyooka, Japan, winner of last week’s Riddler Classic.
Last week, an image of cookies on social media made me wonder how many overlapping circles were needed to fill up a rectangular tray.
More specifically, suppose you had a tray that was a unit square (i.e., with side length 1). Now, if you had four identical circles (i.e., cookies) that could overlap, they needed a radius of at least 0.25·√2 to completely cover the square, as shown below:
For last week’s puzzle, instead of four identical circles, you had five. What was the minimum radius they needed to completely cover the unit square?
It might have been tempting to maintain the symmetry of the four-circle arrangement shown above by inserting a fifth circle in the middle. But in that case, each of the four outer circles still would have had to pass through the midpoints of two of the square’s sides, meaning they couldn’t get any smaller. Therefore, the arrangement had to be a little less symmetric.
Solver Tom Keith gained some intuition about the optimal arrangement with computer assistance, placing small circles at five random points and letting them grow at the same pace, adjusting their positions to increase the total area of the square covered with each step. In the end, Tom’s circles each had a radius of about 0.326:
Meanwhile, solvers Mike Strong and Paige Kester found a trove of solutions for different numbers of circles, courtesy of Erich Friedman. The case of five circles covering a square was proved by Aladár Heppes and Hans Melissen in 1997. The solution turned out to be slightly less than 1/3.065, or (again) about 0.326.
As shown by solver Mark Girard, the minimum radius that resulted in a completely covered square was the solution to a sixth-order polynomial equation: 64x6 − 144x5 + 209x4 − 196x3 + 154x2 − 92x + 21 = 0.
For extra credit, you had six identical circles that can overlap. The tempting answer again involved (too much) symmetry: splitting the square into a grid of two by three congruent rectangles, and then covering each of those with its own circle. This resulted in a radius of (√13)/12, or about 0.3004. But by tilting the relative orientation circles, it was possible to do even better. Indeed, Heppes and Melissen found a radius less than 0.2988 back in 1997. Mark also found the work of Kari Nurmela and Patric Östergård in 2000, which included the following illustration for five and six circles, highlighting radii to points of intersection for each:
This six-circle covering had a radius of approximately 0.2987.
Anyway, all this computation has only served to fuel my appetite … for cookies!
Want more puzzles?
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 firstname.lastname@example.org.