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 lots of 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 👏 Rasmus Ibsen-Jensen 👏 of Vienna, Austria, 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 Pokémon Go puzzle that comes to us from Po-Shen Loh, a math professor at Carnegie Mellon University, the coach of U.S. International Math Olympiad team and the founder of expii.com.
Your neighborhood park is full of Pokéstops — places where you can restock on Pokéballs to, yes, catch more Pokémon! You are at one of them right now and want to visit them all. The Pokéstops are located at points whose (x, y) coordinates are integers on a fixed coordinate system in the park.
For any given pair of Pokéstops in your park, it is possible to walk from one to the other along a path that always goes from one Pokéstop to another Pokéstop adjacent to it. (Two Pokéstops are considered adjacent if they are at points that are exactly 1 unit apart. For example, Pokéstops at (3, 4) and (4, 4) would be considered adjacent.)
You’re an ambitious and efficient Pokémon trainer, who is also a bit of a homebody: You wish to visit each Pokéstop and return to where you started, while traveling the shortest possible total distance. In this open park, it is possible to walk in a straight line from any point to any other point — you’re not confined to the coordinate system’s grid. It turns out that this is a really hard problem, so you seek an approximate solution.
If there are N Pokéstops in total, find the upper and lower bounds on the total length of the optimal walk. (Your objective is to find bounds whose ratio is as close to 1 as possible.)
Advanced extra credit: For solvers who prefer a numerical question with this theme, suppose that the Pokéstops are located at every point with coordinates (x, y), where x and y are relatively prime positive integers less than or equal to 1,000. Find upper and lower bounds for the length of the optimal walk, again seeking bounds whose ratio is as close to 1 as possible.
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 a hungry, but persnickety, grizzly bear. The bear wants to maximize its intake of salmon, but is only willing to eat fish that are at least as big as all the fish it’s eaten already. If the bear will see two or three salmon during its fishing expedition, which weigh something uniformly random between 0 and 1 kilogram, it should always eat every fish it can.
To see why, let’s start with the two-fish case. If the bear eats every fish it can — the “greedy” strategy — its expected fish intake is the expected weight of the first fish plus the expected weight of the second fish given that it’s willing to eat it. Say the first fish has a weight \(x_1\) and the second fish a weight \(x_2\). The expectation under the greedy strategy is
$$\int_0^1 \left(x_1 +\int_{x_1}^1 x_2 dx_2\right)dx_1=\frac{5}{6}\approx 0.833$$
But if he forgoes the first fish, he’ll eat only the second fish, which is only half a kilogram on average. Therefore, always eat the first fish!
A similar argument holds for the three-fish case. We now know that if the bear forgoes the first fish, we’re back to the two-fish case, where it can expect 5/6 kilograms of salmon total. In fact, a nice pattern emerges. If the bear eats every fish it can on an expedition N fishes long, its expected intake is the first N terms of the sum 1/2 + 1/3 + 1/4 + 1/5 + 1/6 … So, for a three-fish expedition, eating the first fish yields 1/2 + 1/3 + 1/4 = 13/12 kilograms on average. Again, always eat the first fish!
But things change if the fishing expedition gets any longer. Laurent Lessard compared optimal bear behavior to greedy bear behavior. For three fish or fewer, these strategies are identical. But for more fish, the bear does well to let certain, heavier fish go early on in the expedition, in order to maximize consumption in the future.
The 🏆 Coolest Riddler Extension Award 🏆 this week goes to Kris Mycroft. Kris transported the problem to the arctic, and looked at the problem faced by polar bears in a network of streams.
Looks like it pays to be the alpha bear at the head of the river.
And, lest you think The Riddler is a mere diversion, comfortably abstracted from the struggles of daily life, the Alaska Salmon Program illustrated the puzzle with real-world bear footage in this delightful Twitter thread:
Elsewhere in the puzzling world:
- Some puzzles on Olympic strategy. [The New York Times]
- Puzzles about a summer birthday party. [The Wall Street Journal]
- A few Olympics problems, right on time. [Expii]
- And, appropriately, a R-I-O puzzle. [NPR]
- A puzzle book of a very different kind. [Wired]
Have a wonderful weekend!