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, the readers. 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 form at the bottom. 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 for the shoutout, I need to receive your correct answer before 11:59 p.m. EST on Sunday — have a great weekend!
Before we get to the new puzzle, let’s return to last week’s. Congratulations to ÑÑâÐ Ian Rhile ÑÑâÐ of Wyomissing, Pa., 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. In a few days, at Madison Square Garden here in New York, a new king or queen of the canine world will be crowned at the Westminster Kennel Club Dog Show. As a tip of the ol’ deerstalker, here’s a classic problem I reworked to feature a very clever dog. Fair warning: This one is tougher than a brand new chew toy.
There is a duck paddling in a perfectly circular pond, and a Nova Scotia duck tolling retriever prowling on the pond’s banks. The retriever very much wants to catch the duck. The dog can’t swim, and this particular duck can’t take flight from water. But the duck does want to fly away, which means it very much wants to make it safely to land without meeting the dog there. Assume the dog and the duck are both very smart and capable of acting perfectly in their best interests — they’re both expert strategists and tacticians. Say the duck starts in the center of the pond, and the dog somewhere right on the pond’s edge. To ensure that the duck could never escape safely, how many times faster would the dog have to be able to run relative to how fast the duck can swim? (Assume the dog is a good boy, yes he is, and thus very patient. The duck can’t simply wait him out. Also assume both animals can change direction without losing speed, and that the duck can take flight safely immediately after reaching shore if the dog isn’t there.)
Need a hint? You can try asking me nicely. Want to submit a puzzle or problem? Email me.
[googleapps domain=”docs” dir=”forms/d/1isRCKZIGo5XhbUbjM9uqkGgVn96u5Kd8UIJMnt2vnx8/viewform” query=”embedded=true” width=”760″ height=”1000″ /]
And here’s the solution to last week’s Riddler, concerning vehicular traffic on a very long highway, which came to us from Django Wexler. I’ve adapted this solution from an excellent submission from reader Aaron Montgomery.
The average number of groups of cars, given a total of N cars, is 1+1/2+1/3+…+1/N. Let’s prove it.
Call the number of groups of cars \(X\). Suppose that the cars are added to the road — placed somewhere randomly on it — one by one in reverse order of speed, with the slowest car added first and the fastest car added last. After each car is added, we wait until all the cars settle into their new positions before adding the next one. Let’s consider what happens when there are \(n\) cars already on the road in some order, in \(X_n\) groups, where \(n\) is a number less than \(N\). Now we add another car, which will be faster than all the cars already on the road. This new car will create a new group if and only if it is the lead car. (It will either speed off in the lead, or it will get stuck behind some necessarily slower car.) It will be the lead car with probability \(1/(n+1)\). Thus,
$$X_{n+1} = \begin{cases} X_n + 1 &\mbox{with probability} \frac{1}{n+1} \\ X_n & \mbox{with probability } \frac{n}{n+1} \end{cases}$$
Let \(E[X_n]\) denote the expected number of groups of cars, given n cars. From above, we now know that
\begin{equation} \begin{split} E[X_{n+1}] &= (E[X_n]+1)\cdot \frac{1}{n+1} + E[X_n]\cdot \frac{n}{n+1} \\& = E[X_n]+\frac{1}{n+1} \end{split} \end{equation}
Combine this with the fact that we know that if there is just one car (\(n=1\)), then there must necessarily be just one group (\(E[X_1]=1\)), and we’re done. If there’s one car there’s one group. If there are two cars there are 1 + 1/2 groups on average. If there are three cars there are 1+1/2+1/3 groups on average, and so on. This series of the average number of groups of cars is known as the harmonic series. Visually, the expected number of groups looks like this, as the number of cars on the road increases:
While it looks like it might plateau at some number of groups of cars, this series never converges! As the number of cars increases to infinity, the expected number of groups increases to infinity as well — just very, very slowly.
Competition for the ÑÑÐâ Coolest Riddler Extension Award ÑÑÐâ was fierce this week. After a series of sleepless nights, and a lengthy, pricey and messy consultation with the haruspex who works above my bodega, I’ve decided that the award goes to [drumroll…] Nick Stanisha. Nick proposed adding a second lane — a “fast lane” — to the highway, and then analyzed optimal driver behavior. His main finding: “The cars can proceed down the highway with the fastest expected speed if the left lane is reserved exclusively for people who travel faster than average.” I thank Nick for his public service, and wish the jamoke on I-278 last weekend had understood how fast lanes are supposed to work. Here is a graphic summary of Nick’s finding:
Three honorable mentions for coolest extension:
Dan Schlauch proposed, “Every hour, the leader of each group of cars looks into the mirror. Upon noticing the traffic built up behind them, they pull over and let the group pass them before continuing on the road. How many hours will need to pass before the n cars are all unobstructed?” Suffice to say his findings made me happy that I live near a subway station.
Meanwhile, some readers got a bit wild. Marty Nguyen proposed teleportation portals on the highway, a la “Portal.”
And Cyrus Hettle emailed to suggest the addition of highway monsters. His email is worth quoting at some length:
We now introduce two powerful creatures, a gnome and a demon, who care deeply about this particular stretch of highway. The gnome is a benevolent being, who wishes speedy travel to all, whereas the demon wishes to inflict as much unpleasant gridlock as he can on this small group of unfortunate drivers. Each has the power to, after the cars are on the road, remove one driver from the road, according to whatever suits his respective wishes (the gnome wants to minimize the average time it takes the remaining drivers to reach their destination, while the demon wants to maximize it).
Cyrus found that interference by the demon led to a slight uptick in average travel time, but interference by the gnome led to a much more significant decrease. Makes sense to me.
And with that, have a lovely weekend!