Kill the Dragon puzzle

Kill the Dragon!

A hapless lost dragon has accidentally landed in a nearby lake. You, the kingdom’s sworn dragon-slayer, have set out on this foggy night to kill it. You are armed with your trusty trebuchet, which can catapult a fiery projectile to any location on the lake. When the projectile hits the water, it will explode in a lethal circle of Greek fire, killing everything within a radius of $r$ metres from the point of impact. Especially dragons.

The fire, however is short-lived, and is extinguished instantaneously. This means the dragon, who swims slowly at a constant speed of $v$ metres per minute, can safely doggy-paddle into a previously scorched area. You can launch one missile per minute.

It’s so foggy, that you can’t tell whether you’ve killed the dragon, which is too tired to leave the lake, and you can’t be bothered to fetch a boat to check. If the lake is a circle of radius $R$ metres, is it possible to aim your volleys strategically to be sure that you will eventually kill the dragon, no matter how it moves?

For which radius $R$ is it possible, and for which is it impossible? What about other shapes of lakes?

This puzzle can be thought of as a sequel to the “Princess in a Castle” puzzle, which I originally found on MathOverflow’s dinner puzzle page. ”Kill the Dragon” was told to me by my friend David, who posed it at a Newcastle mathjam, after exploring a number of similar puzzles, such as the graph-based Princess in a Castle spin-off problem (link also has full solution).

I’ll sketch my solution to “Kill the Dragon” in another post shortly (though I can’t determine every case!).

”Kill the Dragon!” is also quite similar to the well-studied “Princess and Monster” search puzzle, where the monstrous searcher moves within the area at a certain speed instead of being able to check arbitrary locations.

I consider the following puzzle to be the canonical sequel to the original “Find the Princess: Princess in a Castle” (including all the different castle layouts (graphs)): though it seems quite similar to the Castle version, at first glance it appears quite impossible…

Finding the Princess 2: Princess on a train

After searching for many nights and eventually finding the princess, the day before your joyful wedding, she is kidnapped by a moustache-twirling villain! A note informs you she has been tied up on a runaway train somewhere on the kingdom’s only infinitely long train-track, which is moving at a completely unknown (but constant and finite) speed, in an unknown direction.

Fortunately, you have been given access to the track’s maintenance systems, and can check for precisely one second whether the train is between two adjacent signal posts which are placed regularly along the track. Each second you can check one section of track, and once you’ve found the train you can stop it.

Is it possible to find a strategy to guarantee finding your beloved princess in a finite amount of time?

(You may assume the train is 100m long, and signal posts are evenly spaced 1km apart. If you prefer, pick your own values, or make them equal. It hopefully shouldn’t matter.)

Beware: I suspect some ‘undergraduate level’ mathematics is required to solve the train version (my solution does at least). [Update: David Cushing, who is responsible for telling me this puzzle, has written up the solution I gave, as well as setting a further princess problem, on his blog].

“Kill the Dragon” may also be thought of as “Finding the Princess 3: Princess on a Boat”: each puzzle in the series involves searching any particular location you desire at fixed time intervals (hence why the “Princess and Monster” versions do not fit in this category), whilst the princess has movement at a constant speed in an unknown direction. In the train problem however, the captured princess has no control over her movements.

If you do think of the Dragon puzzle as a Princess puzzle, then substituting the Greek fire for a sonar of some sort is recommended. Perhaps the princess is rowing her boat to hide from you: obviously she wants to get out of this puzzling arranged marriage.

(Photo by stungeyeCC)