Can You Solve This Rather Pedestrian Puzzle?

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. If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.

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. 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:

Riddler city blocks

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:

Riddler City diagonal sidewalks

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?

Submit your answer

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:

Riddler City octagonal sidewalks

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?

Submit your answer

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 [email protected].


Footnotes

  1. Important small print: Please wait until Monday to publicly share your answers. In order to 👏 win 👏, I need to receive your correct answer before 11:59 p.m. Eastern time on Monday. Have a great weekend!

Zach Wissner-Gross leads development of math curriculum at Amplify Education and is FiveThirtyEight’s Riddler editor.

Comments

Franklin

Leave a Reply

Your email address will not be published. Required fields are marked *

Next Post

Election Update: The First Polls Since New Hampshire Show No Big Bounces

Sat Nov 30 , 2019
<p>Three days after the New Hampshire primary, we are finally getting some polls that reflect the new state of the race — including a poll in Nevada, the next state in the voting sequence, for the first time in a full month! And overall, they’re not showing that any candidate has grabbed a ton of momentum out of Iowa or New Hampshire. That’s probably good news for former Vice President Joe Biden, whose firewall in Southern states appears weakened but still standing. But mostly it’s a recipe for a long, drawn-out nominating contest. In fact, our <a href="https://projects.fivethirtyeight.com/2020-primary-forecast/">national primary forecast</a> currently says that the single most likely outcome of the primary season is that no candidate gets a majority of pledged delegates.</p>
EU_POLLS-0214-4×3EU_POLLS-0214-4×3
RSS
Follow by Email