Welcome to The Riddler. Every week, I offer up a problem related to the things we hold dear around here: math, logic and probability. These problems, puzzles and riddles come from many top-notch puzzle folks around the world — including you! You’ll find this week’s puzzle below.
Mull it over on your commute, dissect it on your lunch break and argue about it with your friends and lovers. When you’re ready, submit your answer using the link below. I’ll reveal the solution next week, and a correct submission (chosen at random) will earn a shoutout in this column. Important small print: To be eligible, I need to receive your correct answer before 11:59 p.m. EDT on Sunday. Have a great weekend!
Before we get to the new puzzle, let’s return to last week’s. Congratulations to 👏 Espen Jorde 👏 of Oslo, Norway, our big winner. You can find a solution to the previous Riddler at the bottom of this post.
Now here’s this week’s Riddler, a barnstormer of a puzzle that comes to us from Chris Mills, an engineer from Saratoga, California.
You, a hard-driving sheep farmer, are tucked into the southeast corner of your square, fenced-in sheep paddock. There are two gates equidistant from you: one at the southwest corner and one at the northeast corner. An angry, recalcitrant ram enters the paddock from the southwest gate and charges directly at you at a constant speed. You run — obviously! — at a constant speed along the eastern fence toward the northeast gate in an attempt to escape. The ram keeps charging, always directly at you.
How much faster than you does the ram have to run so that he catches you just as you reach the gate?
Extra credit: Let’s offer up a 🏆 Coolest Riddler Extension Award 🏆. Complicate the paddock, alter the ram’s behavior, or even toss another ram in. Or something more creative than that. Submit your extension and its solution via the form below. The winner gets a shiny emoji trophy next week.
Submit your answer
Need a hint? You can try asking me nicely. Want to submit a new puzzle or problem? Email me. I’m especially on the hunt for Riddler Jr. problems — puzzles that can stoke the curiosity and critical thinking of Riddler Nation’s younger compatriots.
And here’s the solution to last week’s Riddler, concerning Pokéstops arrayed in your neighborhood park, and your desire to visit each Pokéstop and return to where you began using the shortest possible route. Your goal was not to find a specific solution, per se, but rather to find upper and lower bounds on the length of the optimal route.
Riddler Hall of Famer Laurent Lessard illustrates how the bounds derive from various specific arrangements of Pokéstops. The upper bound, for example, occurs when all the N stops are arranged in a line. This arrangement makes visiting them all a very lengthy endeavor indeed, as you have to retrace your steps to get back to the beginning, traveling the distance between them twice, for a total of 2(N-1) units. A far more efficient arrangement is a rectangle, in which case, if there are an even number of stops, you’d only have to travel in a circuit of length N.
As much as this riddle appears to be about Pokémon, it’s really about graph theory, which is used in math to describe pairwise relationships between objects. The problem’s submitter, Po-Shen Loh, noted that the bounds on the length of the optimal journey can be found by using the graph theory concept of a minimum spanning tree, which connects all vertices in a graph (Pokéstops in this case) in the most efficient way. The length of the optimal journey is bounded between the weight of the minimum spanning tree of the graph created by the Pokéstops, and two times its weight — it’s possible you’d need to double-back, after all, retracing your steps. This method reveals that the optimal trip will be somewhere between N-1 and 2(N-1) units long.
The extra credit part of the problem presented you with a very specific arrangement of stops, namely Pokéstops located at every point with coordinates (x, y), where x and y are relatively prime positive integers less than or equal to 1,000. As Po explained to me, you can implement the Christofides algorithm, as it is not practical to do it by brute force — there are simply too many possible routes to consider. The point of this Riddler was to get people thinking about the famous Traveling Salesman Problem, which has not seen a breakthrough beyond the Christofides algorithm for decades.
This is some really deep math (and a great plea to your parents for more Pokémon screen time, kids). Again, there’s not a “right” or “wrong” answer here this week (this is really tough computational stuff) other than giving it the old Riddler try. Zach Wissner-Gross illustrates his algorithm in action here:
Zach was able to find a path 773,580 units long, or about 1.3 times the number of Pokéstops. Seems pretty efficient to me!
Elsewhere in the puzzling world:
- Are you a puzzle Olympian? (Spoiler alert: You are in my eyes.) [The Guardian]
- Circles, triangles, spheres and cubes. [The Wall Street Journal]
- Puzzle on phrases and another on the Olympics. [NPR]
Have a super weekend!