Can You Solve This Rather Pedestrian Puzzle?
by Zach Wissner-GrossWelcome 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
Riddler City is a large circular metropolis, with countless square city blocks that each have a side length of 1 km. A small section of the city, composed of 36 blocks, is shown in the diagram below:
At the very center of the city lies Riddler City Hall. Its many employees all walk to and from work, and their homes are evenly scattered across the city. The sidewalks they walk along have always been adjacent to the streets — but that may be changing.
Recently, several city hall employees submitted a petition, requesting that the sidewalks should no longer lie alongside the streets. Instead, they want the sidewalks to cut diagonally across the city, connecting nearby street intersections. These proposed sidewalks are represented by the thicker blue lines in the diagram below:
The mayor of Riddler City has tasked you with resolving this dispute in a mathematical manner. She would like you to answer the following question: What fraction of the city hall employees would have a shorter walk home (that is, to the street intersection nearest to their home) if the city replaced its traditional sidewalks with these diagonal sidewalks?
Riddler Classic
From David Lewis comes an additional, original twist on Riddler City’s urban planning:
The mayor ultimately decided not to pursue diagonal sidewalks, but the petitioners haven’t given up yet. One of them recently visited Barcelona and was inspired by its octagonal city blocks.
Now, there’s a second petition on the mayor’s desk, asking that the grid layout of the city’s sidewalks be replaced with an octagonal pattern, represented by the thicker blue lines in the diagram below:
Under this second proposal, now what fraction of the employees would have a shorter walk home if the city replaced its traditional sidewalks with these new sidewalks?
Solution to last week’s Riddler Express
Congratulations to 👏 Andrew Yuan 👏 of Brisbane, Australia, winner of last week’s recent Riddler Express.
Last week, you were asked to find how many more palindrome dates (in the MM/DD/YYYY format) there would be this century. The most recent occurrence was this past Groundhog Day, 02/02/2020.
As many solvers noted, the fact that the date had to occur in this century meant that it had to have the form MM/DD/20YY. Then, in order to be a palindrome — meaning it reads the same forwards and backwards, if we ignore the slashes — the form becomes MM/02/20YY.
At this point, the two last digits of the year are the same as the digits of the month, but flipped. And so Andrew went through the 12 months of the year to see which resulted in palindromes that hadn’t yet occurred. The 12 palindrome dates are:
- 01/02/2010 (already passed)
- 02/02/2020 (just passed)
- 03/02/2030
- 04/02/2040
- 05/02/2050
- 06/02/2060
- 07/02/2070
- 08/02/2080
- 09/02/2090
- 10/02/2001 (already passed)
- 11/02/2011 (already passed)
- 12/02/2021
Of the 12 possible palindrome dates, four have already passed. That means there are eight palindrome dates remaining this century.
Solver Sami from London extended the riddle, looking also at palindrome dates in the DD/MM/YYYY format (which, appropriately enough, is used in London). Following a similar approach, Sami found 23 such palindrome dates. Interestingly, one of these is Feb. 29, 2092 — a palindrome leap day!
Back in the American format, the next palindrome date will occur on Dec. 2, 2021, which sounds like the perfect time to ask this riddle again. (Spoiler alert: The answer will be seven.)
Solution to last week’s Riddler Classic
Congratulations to 👏 Bram Carlson 👏 of Fort Lauderdale, Florida, winner of last week’s Riddler Classic.
Last week, you were introduced to an ambiguous mathematical expression with absolute values. Offered as an example, the expression |−1|−2|−3| had two possible interpretations, and as a result, two corresponding values:
- The two left bars were a pair, and the two right bars were a pair. In this case, we had 1−2·3 = 1−6 = −5.
- The two outer bars were a pair, and the two inner bars were a pair. In this case, we had |−1·2−3| = |−2−3| = |−5| = 5.
That was all well and good. But instead of analyzing just two cases, you had to find how many different values the expression |−1|−2|−3|−4|−5|−6|−7|−8|−9| could have. Yikes!
As you might have expected, some solvers used pencil and paper, while others turned to their computers. While this riddle seemed imposing, pencil and paper did an excellent job at providing an upper bound for the answer.
For the expression |−1|−2|−3|, there were two ways to pair the absolute value bars, and it turned out there were two possible values — one for each pairing. Similarly, finding the total number of ways to pair the absolute value bars in the expression |−1|−2|−3|−4|−5|−6|−7|−8|−9| gives us all possible values for the expression. (However, not all of these values may be unique — some may be duplicates of each other. But we can cross that bridge when we get to it … in a few paragraphs).
To count up the number of pairings of absolute value bars, we could imagine each pair consisting of an “open” bar and a “close” bar — just like parentheses. In other words, the number of pairings of the 10 bars in |−1|−2|−3|−4|−5|−6|−7|−8|−9| was the same as the number of ways to write out five pairs of — or 10 total — parentheses. Many solvers pointed out that this related problem is quite famous. Given N pairs of parentheses, the total number of valid sequences is known as the NthCatalan number.
Catalan numbers show up all over the place in discrete mathematics and combinatorics. Don’t believe me? Well, try figuring out how many ways you can divide up a convex polygon into non-overlapping triangles by connecting the polygon’s internal diagonals. Go ahead, I’ll wait. What’s that? The answer turns out to be a Catalan number? You don’t say.
Since there were five pairs of absolute value bars in the original expression, |−1|−2|−3|−4|−5|−6|−7|−8|−9|, that meant there were 42 (the fifth Catalan number) total ways to pair up the bars. A few solvers stopped here, satisfied with an answer of 42. Of course.
But, as we said earlier, 42 is just the upper bound for our answer. There can’t be more than 42 unique values, but if some pairings of the absolute value bars result in duplicate values, the answer will be less than 42.
Indeed, there were several such duplicates. Ian Rhile evaluated all 42 interpretations of the original expression and plotted them on a number line:
Of the 42, three were duplicates, meaning there were only 39 unique values for the expression. For anyone who wants to know, this week’s winner, Bram, identified those pesky duplicates: −375, −25 and 105.
A few brave solvers tried their hands at evaluating even longer expressions, like |−1|−2|−3|−4|−5|…|−37|, which Angela Zhou found to have 664,540,593 unique values. (Her poor computer.)
While the number of unique values closely matches the Catalan numbers for shorter expressions, Angela found that they drop off — |−1|−2|−3|−4|−5|…|−33| is the first such expression whose number of unique values isn’t even half of its corresponding Catalan number.
Finally, there’s a tradition here at The Riddler of referencing The On-Line Encyclopedia of Integer Sequences (OEIS). There seems to be a known sequence out there that gives you the answer almost every week. Solver Tyler Barron was delighted to report that no one has yet submitted this sequence — the number of unique values for |−1|−2|−3|−4|−5|…|−(2N−1)| — to OEIS.
And in true Riddler fashion, Tyler called dibs.
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.