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 👏 Chen Yin 👏 of Hong Kong, 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 grizzly bear puzzle that I wrenched from my heretofore repressed memories of econ grad school problem sets.
A grizzly bear stands in the shallows of a river during salmon spawning season. Precisely once every hour, a fish swims within its reach. The bear can either catch the fish and eat it, or let it swim past to safety. This grizzly is, as many grizzlies are, persnickety. It’ll only eat fish that are at least as big as every fish it ate before.
Each fish weighs some amount, randomly and uniformly distributed between 0 and 1 kilogram. (Each fish’s weight is independent of the others, and the skilled bear can tell how much each weighs just by looking at it.) The bear wants to maximize its intake of salmon, as measured in kilograms. Suppose the bear’s fishing expedition is two hours long. Under what circumstances should it eat the first fish within its reach? What if the expedition is three hours long?
Extra credit: It’s been a while, so let’s offer up a 🏆 Coolest Riddler Extension Award 🏆. Lengthen the expedition, change the bear’s preferences, alter the fish population, or something even more creative. 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 the emperor of Byzantium and some traitorous generals. You, the emperor, were meant to confidently identify a loyal general by asking the smallest number of questions of the generals. The loyalists among them always tell you the truth, while the traitors answer any way they please.
If you start with N generals, you can identify a loyal general in at most N-1 questions. Here’s the solution from the puzzle’s submitter, Django Wexler:
The algorithm goes like this: Place all the generals in a pool, and start a counter, K, at N/2 rounded down (that’s the maximum number of traitors). Pick two generals at random, A and B. Ask B about A.
If B says “traitor,” then remove both A and B from the pool and reduce the counter by one. Either B is a traitor and lying, or A is a traitor and B is telling the truth, or both are traitors. Regardless, we have removed at least one traitor from the pool. Start over.
If B says “loyal,” we now know that either A is loyal or B is a traitor. So A can be a traitor if and only if B is also a traitor.
Pick another general from the pool, C. Ask him about B. If he says “traitor,” throw B and C out as above. If he says “loyal,” we know that for A to be traitor, B must be, and for B to be, C must be. Then grab D, and so on.
Eventually, either
- K will reach zero because you’ve thrown out N/2 pairs. Since you started with more than half of your generals being loyal, there will be some generals left in the pool, and they are guaranteed to be loyal, or
- the “chain” of generals that must all be traitors in order for A to be a traitor will be longer than the counter K. Since K represents the maximum number of traitors left in the pool, at that point A is guaranteed to be loyal.
The most pessimistic case will be a chain that almost reaches K, then gets a series of false answers, then builds up again, and so on. You never end up asking a question of the guy you find to be loyal, and you ask each other guy a maximum of once, so the worst-case number of questions is N-1.
Elsewhere in the puzzling world:
- At long last! Some Pokemon Go puzzles. [Expii]
- A puzzle about basketball playing time. [The New York Times]
- Can you outfox the desert island despot? [The Guardian]
- Some word puzzles from the puzzlemaster Will Shortz. [NPR]
- Some puzzles to celebrate Geometry Day. [The Wall Street Journal]
Have a fantastic weekend!