18
$\begingroup$

The devil has trapped you in his playground.

enter image description here

The devil knows that you can't cross over the burning boundary of his circle, so he allows you to choose a position within the circle before he starts to chase you down. You know that

  • You and the devil move at speeds $V$ and $1$ respectively.
  • Both move simultaneously and continuously, in any choice of direction.
  • Radius of the circle $R=1$.
  • The devil leaves an uncrossable burning track along his trajectory:

enter image description here

You're caught by the devil if the distance between you is $0$. The devil will try to catch you as quickly as possible. You know that an angel is en route to save you, so you move to survive for as long as possible.

Question 1: How long can you manage to survive if $V=1$? How should you move?

Question 2: Suppose now you move twice as fast as the devil, i.e. $V=2$. How long can you manage to survive?

Question 3: As your speed $V$ approaches infinity, how long can you manage to survive?

Hint

Notice that you can survive for at least $T=2$ by choosing to stay at the opposite side of the devil. On the other hand, you can't survive indefinitely no matter how fast you move, because the devil can carve the disk into patches of exponentially decreasing areas with you inside, shrinking that area to $0$ in finite time.

$\endgroup$
6
  • 1
    $\begingroup$ But what is the devil's strategy? While he can move in any direction, which would he choose at any time? A deterministic devil strategy seems important for anyone else to develop a counter-strategy. $\endgroup$
    – bobble
    Sep 5, 2021 at 15:29
  • 2
    $\begingroup$ @bobble The devil tries to catch you as quickly as possible. He's current optimal velocity depends on your relative positions and your current velocity. $\endgroup$
    – Eric
    Sep 5, 2021 at 15:36
  • 2
    $\begingroup$ Regarding the hint: if I'm understanding correctly, I don't think it's correct. Can the devil really shrink the area to 0? The area can certainly approach 0, but the line of fire has no width. $\endgroup$
    – Alira
    Sep 5, 2021 at 18:08
  • 2
    $\begingroup$ @Alira That is essentially like Zeno's paradox. The fact that each subdivision takes the devil a proportionally smaller amount of time means that this is a supertask. In my opinion this is a supertask that does make sense and can be completed so that a zero area is reached in a finite time, but opinions can differ. $\endgroup$ Sep 6, 2021 at 6:45
  • 1
    $\begingroup$ @Alira, I was confused at first, but check out this answer for a similar dilemma. $\endgroup$
    – justhalf
    Sep 6, 2021 at 7:39

4 Answers 4

9
$\begingroup$

You're screwed in constant time, no matter your speed, since the devil has a good strategy.

I cannot claim to having found the devil's optimal strategy, but I do claim that there is an upper bound to the time the devil takes to catch the victim. And that upper bound is quite low.

Assume that the circle is inscribed in an equilateral triangle of ABC of base $b = 2\sqrt[]3$, with the devil resting at the midpoint D of its base AB, like so:

initial triangle

In fact, forget about the circle. Also, mark the midpoint of BC as E, and of CA as F:

triangle with midpoints

The devil shall move a distance of $b/2$ from D towards E, dividing it in two areas. Mark the midpoint of DE as G:

triangle divided once

Is the victim within the smaller triangle BDE? Good, move $b/4$ towards G, and repeat this division algorithm on the BDE triangle. If not, move $b/2$ from E to F, marking the midpoint of EF as H:

triangle divided twice

Again: is the victim in the smaller triangle CEF? Good, then move $b/4$ back to H and repeat. If not, divide the remaining rhombus in two by moving $b/2$ from F to D, marking the midpoint of DF as J:

triangle divided thrice

...and since the victim sure is either DEF or ADF, move $b/4$ from D to J, and repeat the algorithm. The idea is to divide the triangles into smaller and smaller triangles in a methodical way.

Note several important facts about this strategy:

- Every time a triangle is divided in four, its area is divided by four

- Each time a triangle is divided in four, its base is divided by two

- In order to divide a triangle in four, the devil must move at most a distance equal to $7/4$ times its base: $1/2$ each move from midpoint to midpoint, maximum three such moves (D→E→F→D), plus $1/4$ to set up in the midpoint of the appropriate side of a subdivision (E→G, F→H or D→J).

Thus, the first subdivision takes (at most) $\frac{7\sqrt[]3}{2}$; since the triangle's base is halved, the second one takes $\frac{7\sqrt[]3}{4}$, the third one $\frac{7\sqrt[]3}{8}$; and in general the $n$-th one shall take $\frac{7\sqrt[]3}{2^{n}}$.

If the devil could perform these subdivisions an infinite number of times, then the area of the triangle containing the victim would be $\lim_{x \to \infty} \frac{a}{4^x} = 0$. (The initial area doesn't matter so why bother calculating it).

Now, is it possible to move long enough to perform all the subdivisions in a finite amount of length? That's the same as asking "Does the following infinite sequence converge?" $$\sum_{n=1}^{\infty} \frac{7\sqrt[]3}{2^{n}}$$ Since I absolutely suck at doing these calculations (and I have completely forgot the "infinite sequences" chapter from my calculus classes), I cheated a bit by using wolfram-alpha. The sequence does, in fact, converge, to $7\sqrt[]3$ or about 12.124 units of length.

The victim's strategy would be

to lead the devil's movements by an infinitesimal distance, so the devil cannot choose the right subdivision until said subdivision is complete.

The generalized strategy explained above provides an upper bound for the distance the devil must move, but has two characteristics that intuitively look like problems: (a) the devil backtracks, potentially wasting movement and (b) the search space is way bigger than needed.

The backtracking issue can be optimized by

using right-angled isosceles triangles instead of equilateral triangles, and positioning the devil at the right-angle corner. Any such triangle can be halved into two right-angled isosceles triangles, like so:

halving an isosceles triangle

As before, the devil splits a triangle, checks the subdivision containing the lost soul, and recursively proceeds to split that. The devil will follow a fractal path looking like:

fractal path

At each subdivision, the area halves; that means the area converges to zero as before since $$\lim_{x \to \infty} \frac{a}{2^x} = 0$$ The height of the triangles (i.e. the length of the devil's path) shrinks by a factor of $\frac{\sqrt[]2}{2} ≃ 0.7071$ on each subdivision; assuming that the length needed to perform the first subdivision is $\frac{\sqrt[]2}{2}$, then the length needed to perform the $n$th subdivision shall be $$\left(\frac{\sqrt[]2}{2}\right)^n$$, and the total length of the devil's fractal path shall be $$\sum_{n=1}^{\infty} \left(\frac{\sqrt[]2}{2}\right)^n$$.

That seems to solve the backtracking issue, but what about the wasted search space? A possible approach would be for the devil to start moving on a path like...

Starting path for isosceles subdivision

Which means: Starting at A, move to B. Choose the half circle containing the victim (the diagram only shows a solution for the bottom half; the solution for the top half is symmetrical), then proceed to C (ABC). If the victim is within BCD, move to D then start the fractal subdivision of BCD. Else, move to E (ABCE). If the victim is within BCE, start the fractal subdivision of BCE. Else, move to F (ABCEF). Start the fractal subdivision of either EFH or EFG, depending on which of those two triangles contains the victim.

The (worst case) length of the initial path ABCEF is $4 + \sqrt[]2$; and since the distance from F to the midpoint of either EG or EH is $\frac{\sqrt[]2}{2}$, we can use the infinite series described before, so the total length of the devil's path is given by $$4 + \sqrt[]2 + \sum_{n=1}^{\infty} \left(\frac{\sqrt[]2}{2}\right)^n$$ and after cheating a bit with wolfram alpha to solve the infinite series, that becomes: $$4 + \sqrt[]2 + 1 + \sqrt[]2 = 5 + 2\sqrt[]2 ≃ 7.82843$$

That's significantly better than before (better for the devil, not for the poor soul), but I suspect that it's still not the lowest upper bound possible. The victim's strategy would remain unchanged, and would still depend on knowing the devil's optimal strategy.

$\endgroup$
0
0
$\begingroup$

If the devil always chases straight after me, following my movements tropistically, then

it seems like I should be able to always stay one step ahead of him at any speed, and lead him on a convoluted meditation-labyrinth-style path almost indefinitely.

But if he's smarter than that,

he'll probably ignore my location altogether and just keep hemming me into smaller and smaller patches of the disk, as the hint suggests. devil's playground path

In that case, my instinct would be to cower on the other side of the circle (or circle portion) from him (i.e., first near point 1, then 2, then 3, then 4, etc. -- where he aims each time to cut the portion I'm in again in half), and dodge to one side or the other at the last moment. (I use the word "cower" even though the question says I move continuously -- I'm assuming little jittery back-and-forth movements would amount to the same thing as staying still for all intents and purposes. [Also the hint uses the word "stay".)

But I must be missing something, because variations in my speed wouldn't seem to matter to this solution, as long as I can move at least as fast as him.

$\endgroup$
1
  • $\begingroup$ Of course you are missing something big. D does not have to follow the halving algorithm, so you cannot assume that in escaping. $\endgroup$
    – user21820
    Nov 3, 2021 at 20:53
0
$\begingroup$

Though at first instinct getting as far away as possible from the devil sounds good, I think a good strategy would be to

position yourself close to him, very near to the perimeter of the circle. Then move around the perimeter at the same speed as the devil, slowly spiraling toward the center. The closer to the devil that you start, the wider will be the remaining space after circling. Also the closest you can come to the fiery trail, the bigger you can make the spiral. That will allow for a lot of time for the angel to come and zap the devil.

Note that this will only work if the devil just chases mindlessly by the shorter path to you. If the devil is more interested in strategy than chasing, you're doomed. Also this requires a speed equal or faster than the devil.

$\endgroup$
3
  • $\begingroup$ This sounds to me like the same thing as the first paragraph of C. P. Boyko's answer from September 2021. Am I missing something? $\endgroup$
    – Gareth McCaughan
    Feb 2, 2022 at 14:24
  • $\begingroup$ His strategy was a "convoluted meditation-labyrinth-style path". This one is simpler, and does not mess up (i.e. dead ends) like a laberinthical one would. $\endgroup$ Feb 2, 2022 at 15:17
  • $\begingroup$ Maybe I'm misunderstanding CPB's idea, but my interpretation of what he meant was exactly the sort of spiral you're proposing. (It is very possible that I'm misunderstanding his idea, which I guess means that stating it more clearly and explicitly is valuable even if I'm right :-).) $\endgroup$
    – Gareth McCaughan
    Feb 2, 2022 at 21:02
-1
$\begingroup$

This is a strategy that I think the devil should be using, but I don't have a proof that it works. Maybe someone else can supply either a proof or a counterexample.

Consider V=1 first. The devil starts by moving to the center of the circle completly ignoring you. This takes 1 time unit. At this point the devil is at distance at most 1 from you. Therefore any point you can reach at time T=2 the devil can reach by T=2 as well. That is what the devil will aim for.

At any time t in [1,2] the devil will look at your velocity (as a vector) and assuming you continue moving at that exact speed and in that direction compute where you will be at T=2 and then move at maximum speed towards that point. I'm fairly sure that this guarantees that the devil will have caught you at T=2 at the latest but I don't have a proper proof.

This should also generalize to V>1. Either by looking farther into the future or by first carving the circle into smaller pieces one should be able to use essentially the same strategy.

$\endgroup$
4
  • $\begingroup$ The devil tries to catch you as quickly as possible. I don't think any strategy that ignores your position at any time is a solution, since there's the possibility the devil walks right past you and misses an opportunity to catch you earlier. Large discrete time steps also aren't helpful - with discrete steps, the devil can only close the distance to you from T=1 to T=2, but you may have the option to start walking away from the devil in that period. If you assume constant speed from T=1 to T=2, why not T=0 to T=2? $\endgroup$ Dec 2, 2021 at 20:41
  • $\begingroup$ @NuclearHoagie My claim is that the devil will get you at T=2 the latest no matter what you do. That doesn't mean he can't get you earlier if you are helpful. The catching strategy is meant to apply at all times from T=1 to T=2, so if you change your speed or direction the devil will instantly adjust as well. $\endgroup$
    – quarague
    Dec 2, 2021 at 20:48
  • 1
    $\begingroup$ That doesn't work. At T=1, suppose you're on the edge of the circle and the devil is in the center. You start walking directly toward the center, so the devil expects you to arrive there at T=2 and therefore stays put. At T=1.5, you turn around and head directly back to the edge. The devil now heads there, and catches you at T=2.5. You can do the same thing with infinitesimal time steps by walking along the circumference and then back to where you started. If you can get the devil to walk any path other than a straight line across the circle, you can last longer than T=2. $\endgroup$ Dec 2, 2021 at 20:58
  • $\begingroup$ If you move along the edge and change direction, the devil's path from the center isn't straight so it's longer than 1. $\endgroup$ Jan 2, 2022 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.