Kill the Dragon: a solution

This is my solution to the “Kill the Dragon!” puzzle. Improvements, in both the bounds and formality of the argument, are definitely possible.

The solution comes in two parts: firstly, establishing an upper bound R_U, such that lakes with larger radii are impossible to search; secondly finding a lower bound R_L, such that lakes with shorter radii are possible to search.

Some initial observations:

When we clear an area, at worst the dragon could have been on the border. Though the Greek fire may disappear instantaneously, the dragon can move at most v metres into the searched area with a minute. If we fire a shot into the middle of the lake, the searched circle shrinks from a radius r to a radius r-v after one minute (assuming r > v). After t minutes the searched circle will have radius \max(r-tv,0).

So a good start is to ignore the dragon completely, and think of the problem as this:

  1. We add a fiery circle inside the lake.
  2. If we have covered the whole lake with fire, then we’ve won.
  3. The fire retracts v metres from any surrounding water, which is not aflame (or land).
  4. Go to 1.

This may even be a slightly better model of sticky Greek fire, which is essentially an ancient naval napalm, than merely assuming it disappears instantly: however, the two are equivalent here. Note that the fire doesn’t retract from land and other fire, so we may be better off adding our circles touching land or other circles.

If v > 2r then it is impossible, unless we can finish in one fire-volley: ie. R \leq r. For most shapes the same argument will work for v \geq r: we simply can’t get started.

Given any hard maths puzzle, you should always feel free to simplify it, so I’ll start off by considering rectangular lakes, instead of circular lakes.

Rectangular lake, upper bound

Let’s take a rectangular lake of width w (and length longer than this), and r < \frac{w}{2}. Suppose we are part way through solving the puzzle, and have already filled up some area of the lake with fire (for concreteness, suppose we’ve filled it about half-way). I claim* that the best possible set-up we could give ourselves is if the most Southerly part of the lake is filled up, so the edge of the flames that touches the water is a straight line of length w. After one minute, we will lose an area of vw metres squared. If we try any other line, straight or wiggly, I claim the area lost will be greater than this. See (*) far below for more formal arguments.

However, the most area we can add, is the area of a full circle: \pi r^2. So simply, if at any stage the area lost is more than the area of fire gained, then the lake is impossible to fully cover in flames.

In particular, a rectangular lake is impossible to search if \pi r^2 \leq wv, or rather w \geq \frac{1}{v} \pi r^2.

Rectangular lake, lower bound

Now, to show a lower bound, we need to show it is possible for some rectangles. We actually need to construct a strategy. If you’ve tried putting some circles down already, you’ll have noticed that it’s hard to get any sense of what’s going on.

So instead of placing circles, what happens if we place squares of fire? Simplifying the problem again seems like cheating, but this is allowed if we handicap ourselves. We can a fit square within our ring of fire, and just ignore the excess (giving an advantage to the dragon, who we’ve largely forgotten about). If we can cover the rectangle with the smaller squares, then the same strategy will work if we replace the bits we previously ignored. This is proving a stronger result.

Now we are placing squares of side s, where by Pythagoras, s= \sqrt{2} r, how do they shrink? An isolated square will shrink in a similar way to the diameter of an isolated circle, to a square of side s-2v. Still, the water will quench the fire within a distance of v every minute. However, since we are purely dealing with nice straight edges, we don’t want curves being introduced, as can happen at concave corners of fire. So we can handicap ourselves further by straightening these out (in mathematical terms, we will measure the dragon’s movement in the \ell_{\infty} norm instead of the Euclidean \ell_2 norm, and this is allowed as \|x\|_2 \leq \|x\|_{\infty} for all x \in \mathbb{R}^2.)

This time we will use an inductive argument. Let’s start with some Southern area already filled in, a block of height h. We will fill in a new row before we lose too much of the existing fiery area. First, place a flaming square in the corner. Now let the water encroach after a minute. Our next square goes in the newly formed corner away from the land: see how it still fits snugly despite the decay?

Continue in this way: just before the (k+1)th move is made, the situation is as in the drawing below:

We will have finished enflaming a row on the Nth move as soon as (N-1)(s-v) + s \geq w. This will give us a rectangular region, similar to the one we started with. At the beginning of the (N+1)th go, the height of this block will be h+s-Nv. We have made progress in adding area if and only if this new height is strictly greater than the old height h+s-Nv > h.

To put this more formally, we finish after N = \lceil \frac{w-v}{s-v} \rceil moves and have made progress if and only if s>Nv. Certainly \frac{w-v}{s-v} + 1 > N and so progress will be certainly be made if s \geq \left( \frac{w-v}{s-v} + 1 \right)v (note, we’ve dropped the only if, because we’ve dropped some inequality information about whole number discreteness).

Carefully rearranging this, progress is made if \frac{1}{v}(s^2 - 2sv +2v^2) \geq w. Replacing s with \sqrt{2}r we see a rectangle of width w is possible to check if:

\frac{2}{v}(r^2 - \sqrt{2}rv + v^2) \geq w.

I claimed this held by induction, but I seemingly forgot the base case: however, we can easily see that we can get started from a completely calm, unchecked rectangular lake, simply by handicapping (yawn) again. Imagine that the Sourthernmost land is in fact some area in a larger rectangle of the same width covered by retreating flames. Then we can certainly get started, using the above argument.

Rectangular lake, slow dragon

If we assume r>>v, then rv and v^2 are very small compared to r. In this case, further simplifying, rearranging what we know and putting it all together, means we aren’t really sure what happens with rectangular lakes with widths in the range:

2 < \frac{wv}{r^2} < \pi.

This is a nice way of expressing what we still don’t know, as happily the two expressions are of same form after the slow dragon approximation. This equation means that, we can roughly understand the lower bound argument in terms similar to the first: we can replace squares faster than the fire withdraws, as we can place those squares efficiently.

Circular lake, lower bound

So now we’ve found some rectangles where it is possible ensure killing the poor, defenceless dragon. But what about the circles?

If we can cover a rectangle that completely contains the circle, then (yes, technically, by handicapping ourselves), we can certainly cover the circle at the same time. As we can cover a square of side w_L (the largest width of rectangle we know is possible), that means:

R_L = \frac{w_L}{2} = \frac{1}{v}(r^2 - \sqrt{2}rv + v^2).

What improvements could we make to improve this bound?

  1. Cover a smaller shape, which is closer to being a circle. However, the next section will attempt to convince you that the diameter is the most important part to cover.
  2. Understand circle coverings better: these circles covering circles could give you some ideas.
  3. Try covering a hexagon with hexagonal areas or fire?
Circular lake, upper bound

The safest, simplest upper bound would be to find R_U = \frac{w_U}{\sqrt{2}}, given by fitting the smallest square known to be impossible (width w_U) inside the circle.

R_U = \frac{\pi r^2}{v \sqrt{2}}.

Bound to be better?

There is surely room for improvement, if we are very careful. In the rectangular lake, I very carefully assumed that the width was smaller than the length. At first I vaguely believed that if our circle contains a copy of a w_U by 2v rectangle, then it will be impossible. Now I’m not so sure.

This was based on the assumption that a segment was the shape that loses the least area of any fixed area of fire: whilst trying to cover the upper half of this rectangular region, I assumed we would be losing at least vw_U per minute, as in the rectangular case. This isn’t really true*.

(*) Claim investigations 

I’m going to claim without proof that for the circle (and rectangle) that, for all shapes with a given area (at least when sufficiently close to half the total), to minimise the area lost:

  1. The shape should share a border with the boundary.
  2. The shape should be connected.
Let’s look at the rectangle case first. Let’s also assume the fire-water boundary passes between the two longest sides, sufficiently far from the short ends. If the dragon can only move north-south (we may handicap our opponent for the impossible case!), then the area lost is smaller than if it is free to move any way it chooses. In this restricted case the area lost is vw.

The area lost is proportional to v \times \text{length of fire-water edge}. In the limit as v gets smaller and closer to 0, the proportion gets closer and closer to 1. That means minimising the area lost is similar to minimising the perimeter, the length of the fire-water edge.

If the perimeter starts and ends on adjacent edges, you can use one or two mirrors to make a complete shape, all of whose edges are fire-water edges. This means that the shape with the least perimeter for a given area (isoareal, unless there’s a better term) is the same as the shape with the least area for a given perimeter (isoperimetric). Isoperimetric arguments seem to be much simpler than isoareal arguments. A circle famously satisfies both of these equivalent conditions. However, in our two cases, we mustn’t touch the other other edges. However, we can still apply a convexity argument in most cases: we generally want our shape to be convex. I still firmly believe in these two cases it is impossible to enclose approximately half the lake area within a perimeter of length w, as is possible when the perimeter starts and ends on the two longer edges of the lake.

How about the circle? Some of the arguments above make some sense in the circle case, as well.

My equivalent claim for the circle, would be that of all shapes with the same area, the perimeter is least for a segment of the circle. The perimeter is therefore the length of the chord. Is this isoareal claim true?

If we make the same two assumptions (boundary-sharing and connectivity) as for the rectangle, we can imagine the two points where the perimeter touches the lake’s edge as having a chord between them. Set this chord as lying in an East-West direction, by rotating the lake. Then the ‘handicapping the dragon to only North-South movement’ (perpendicular to the chord) argument holds: this is where the better upper bound estimate above comes from.

Again, we only need to the isoareal claim to be true when close to half the area \frac{1}{2} \pi R^2. One possible contender would be to have the perimeter the reflection of the lake arc, so it encloses a ‘double segment’. The area of this segment would be R^2 (\theta - \sin \theta) for some angle \theta, with arc length R \theta. If we set the area to be half of the circle, the arc length is about 2.3R. Clearly the 2R of the diameter is better, vaguely supporting my case. Calculations show this is a suboptimal choice minimising the perimeter for nearly all areas, but this is far from being a proof of the full claim. Perhaps some other circular segment is better?

If we restrict ourselves to looking at areas less than half the lake’s, then the following are equivalent:

  1. The least perimeter for a given area is a segment.
  2. The greatest area for a given perimeter is a segment.

The reason for this is the area of a segment and the length of a chord are related by a bijection. The area of a segment is greater for a longer chord, smaller for a shorter chord.

Unfortunately, neither of these equivalent statements is true.

For a string of fixed length attached to a shorter straight stick, the maximum area enclosed is given when the string forms an arc of a circle. If we take the string length to be a given perimeter, and the stick to be some chord we can work out the area. We can therefore work out the area for some fixed perimeter, varying the chord length. For calculations it is easier to use the angle of the arc \phi, which depends on the chord length and perimeter, instead of the chord length. At \phi=0, the area is just the segment area. At \phi = 2 \pi the area is simply the area of a circle with circumference equal to the fixed perimeter (only just touches edge of lake).

Here’s two graphs, when the perimeter is 2, and when \sqrt(2).

Graph showing that semi-circle maximizes area for perimeter = 2.

Graph showing that segment does not maximise area for a perimeter < 2.

This leaves the idea for a better bound in a bit of a pickle. If you’re not happy with disproving statement 1 via statement 2, you can give an explicit counterexample. As I haven’t bothered explaining the equations (they seem a bit fiddly), it may not help giving the precise values.

If you can reliably calculate the minimal perimeter for a given area, then you can probably adapt the argument for getting a better circle upper bound given above. Specifically we need some interval of areas, greater than what we can add at each stage (so we must ‘pass through it’), with a known lower bound on the area lost for all shapes with areas in the interval.



Filed under Puzzle

3 responses to “Kill the Dragon: a solution

  1. Pingback: Weekly Picks « — the Blog

  2. Andrew.

    I reckon if I’m allowed to use squares of fire of side length 2 metres, and one of these squares of fire every second, and the dragon swims at a rate of less than 1 metre a second, then I can clear a dragon out of a pool with dimensions 2 by 100 metres.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s