Can you escape from the monster and reach the shelter?
You are stranded in the middle of a road in a vast desert, and
there is a monster sitting somewhere out there on the road (you don't know
in which direction), staring toward your location, waiting to eat any one
it can see.
The monster's range of vision \(v\) (meters) is greater than your
range of vision \(w\)
(meters), and once the monster sees you, then you will
instantly be eaten up (the monster can run with
essentially infinite speed).
Shelter You Monster
---X----------X-----------------X---
There is also a shelter on the road in the direction opposite
to that of the monster (see diagram above), but you can't see the shelter,
and you don't know in which direction it is.
Luckily, the shelter is closer to you, by \(c\) (meters), than the monster.
Also, you know the values of \(v\), \(w\), and \(c\).
Determine, with proof, a necessary and sufficient condition
(on \(v\), \(w\), \(c\)) that guarantees that you can reach the shelter
with a suitable strategy.
Describe in detail your strategy to reach the shelter under
this condition. (Assume \(v \gt 0\), \(w \gt 0\), \(c \gt 0\).)
The solution of the problem is given by the following proposition.
You are guaranteed to reach the shelter with a suitable
stratgey (described below) if and only if \(c \gt v - w\).
Detailed proof of the proposition.
\(\newcommand{\dist}{\operatorname{dist}}\)
Shelter You Monster
---S--------------------0----------------------------------M---
dist(S,0) dist(M,0) = dist(S,0) + c
Figure 1
In Figure 1 above, your initial location is shown as the origin, \(0\).
The shelter \(S\) is on one side and the monster \(M\) is on the other side.
By the given condition, you know that \(\dist(M,0) = \dist(S,0) + c\).
In Figure 2 below, two more points \(E\) and \(C\) are shown.
The point \(E\) is \(w\) meters from the shelter, and
is your "escape point": It is the point nearest to you from which
you can sight the shelter \(S\). The point \(C\) is \(v\) meters from
the monster, and it is the dangerous "capture point", the farthest point
that the monster can see from its location \(M\).
Shelter Escape You Capture Monster
---S----------E---------0-------------C--------------------M---
| | | |
|<-------->| |<------------------>|
w v
Figure 2
Starting from your initial position \(0\), if you can reach \(E\)
before reaching \(C\), then you can see the shelter, and escape to it.
On the other hand, if you ever go to \(C\) or beyond, you will be
captured by the monster. So your goal is to ensure that you can
reach \(E\) without getting to \(C\).
We will show that you are guaranteed to reach the shelter
with a suitable stratgey if and only if the escape point \(E\)
is closer to you than the capture point \(C\) (which makes intuitive
sense), that is, if and only if \(\dist(E,0) \lt \dist(C,0)\).
This will prove the proposition, since the condition
\(\dist(E,0) \lt \dist(C,0)\) is equivalent to the condition
\(c \gt v - w\):
\begin{align*}
&\dist(E,0) \lt \dist(C,0)\\
\iff &\dist(S,0) - w \lt \dist(M,0) - v\\
\iff &\dist(S,0) - w \lt \dist(S,0) + c - v\\
\iff &c \gt v - w.
\end{align*}
First we show that if \(\dist(E,0) \geq \dist(C,0)\) then there is
no strategy guaranteeing your escape, that is, no strategy can
guarantee that you will reach the escape point \(E\) before
reaching the capture point \(C\). So assume \(\dist(E,0) \geq \dist(C,0)\),
as shown in Figure 3 below, where we have also shown the point \(C'\)
which is the reflection image of \(C\) about the origin, with
\(\dist(C',0) = \dist(C,0)\).
Shelter Escape You Capture Monster
---S----------E---C'--------0---------C--------------------M---
| | | |
|<-------->| |<------------------>|
w v
Figure 3
The open interval from \(E\) to \(C\)
(the stretch from \(E\) to \(C\) excluding the
end points \(E\) and \(C\)) is the "indeterminate region":
If you are in this region, the monster can't see you and
you can't see the shelter. So long as you are in this region,
you will be safe, but you will also have no idea which way
the shelter is and which way the monster is. So, any strategy
that guarantees your escape must be essentially ambidextrous
(about direction). Now, under any strategy that guarantees your
escape, it must be possible to reach \(E\) before reaching \(C\),
and so it must be possible to reach \(C'\) before reaching \(C\).
However, by the ambidexterity just mentioned, under that strategy
it must also be equally possible to reach \(C'\) before reaching \(C\).
Therefore, if \(\dist(E,0) \geq \dist(C,0)\) (i.e. \(E\) is further away
from you than \(C\) or equidistant), then no strategy can guarantee
that you will reach the escape point \(E\) before reaching the
capture point \(C\). Thus the condition \(\dist(E,0) \lt \dist(C,0)\)
is necessary for the existence of a strategy ensuring your escape.
Next, we show that the condition \(\dist(E,0) \lt \dist(C,0)\)
is sufficient for the existence of a strategy guaranteeing
your escape. Suppose that \(\dist(E,0) \lt \dist(C,0)\),
that is, \(\dist(C,0) - \dist(E,0) \gt 0\).
The following strategy will then ensure that you will reach
\(E\) before \(C\). First note that even though you do not
know the individual numbers \(\dist(C,0)\) and \(\dist(E,0)\),
you can compute their difference \(\dist(C,0) - \dist(E,0)\)
because:
\begin{align*}
&\dist(C,0) - \dist(E,0)\\
=\; &(\dist(M,0) - v) - (\dist(S,0) - w)\\
=\; &\dist(M,0) - \dist(S,0) + w - v\\
=\; &c + w -v,
\end{align*}
and you know the values of \(c\), \(w\), and \(v\).
After computing \(\dist(C,0) - \dist(E,0)\) as \(c + w - v\),
choose and fix any number \(h\) satisfying
\(0 \lt h \lt \dist(C,0) - \dist(E,0)\).
This positive number \(h\) will be your "step size".
You will make several bidirectional
round trips, increasing the radius of the span of your trip
by \(h\) at each step.
The first step of your strategy is to walk a distance of \(h\)
in one direction, turn around, come back to your origin,
walk a distance of \(h\) in the other direction, and come back
to your origin again. (It doesn't matter which direction
you choose to go first, east or west.) In this first trip,
you will span the interval \([-h, h]\), and note that
you are guaranteed not to be captured since \(h \lt \dist(C, 0)\).
If you are lucky, the shelter may be visible during your
first trip (if the point \(E\) is in the interval \([-h, h]\)),
and you will be done; otherwise proceed to Step 2.
In Step 2, you do a similar back-and-forth trip, but this time
spanning the interval \([-2h, 2h]\). If you couldn't see the
shelter yet, proceed to Step 3 to span \([-3h, 3h]\); and so on.
This strategy then guarantees that you will reach \(E\) before \(C\),
that is, you will see the shelter (and escape to it) before the
monster could see you.
To see this, consider the (unique)
least positive integer \(n\) such that
the interval \([-nh, nh]\) contains the point \(E\).
(Although this \(n\) exists and is unique, you won't know
its value initially.)
Then the point \(E\) is in \([-nh, nh]\)
but not in \([-(n-1)h, (n-1)h]\), that is,
\((n-1)h \lt \dist(E,0) \leq nh\).
But then
\begin{align*}
\dist(C,0) &\gt \dist(E,0) + h\\
&\gt (n-1)h + h\\
&=\, nh,
\end{align*}
so \(C\) is not in \([-nh,nh]\). Therefore,
for this particular value of \(n\),
in your \(n\)-th trip you will span the interval \([-nh, nh]\)
and so you will be able to see the shelter but the monster won't be
able to see you. (You will not know the value of \(n\) beforehand,
but you will know that such an \(n\) exists, and so you will know that you
will surely be able to escape to the shelter.)
QED.
The problem implicitly assumes that you must stay on the road
when searching for the shelter. Olivia Racette of Stoney Creek
High School proposed an alternative
solution where you are not confined to the one-dimensional road.
