This week’s Riddler Classic is a pursuit problem with a twist. Here is the problem, paraphrased.
You are walking in a straight line (moving forward at all times) near a lamppost. Your evil twin begins opposite you, hidden from view by the lamppost, as illustrated in the figure below.
Assume your evil twin moves precisely twice as fast as you at all times, and they remain obscured from your view by the lamppost at all times. What is the farthest your evil twin can be from the lamppost after you’ve walked the 200 feet as shown?
Here is my solution.
[Show Solution]
Let’s place the lamppost at the origin of a cartesian plane. We start at $(-1,-1)$ and move toward $(1,-1)$. Here, we are using units of 100 feet. The problem does not say anything about our speed, just that we move forward at all times. So let’s assume our position is given by $(q(t),-1)$, where $-1\leq q(t)\leq 1$ and $q(t)$ is an increasing function of $t$.
Let’s assume our evil twin’s position is $(r(t),\theta(t))$ in polar coordinates. We are told the evil twin always remains occluded by the lamppost. This means the angle we make with the lamppost must match that of the evil twin. In other words,
$$
\cot(\theta) = -q.
$$Next, our evil twin is $k$ times faster than us. Since an increment of position in polar coordinates is given by $(\mathrm{d}r, r\,\mathrm{d}\theta)$, we conclude that:
$$
\dot{r}^2 + r^2 \dot\theta^2 = k^2 \dot q^2,
$$where the dot indicates derivative with respect to $t$. In the two equations above, $q,r,\theta$ are functions of time $t$, but I omitted the $(t)$’s to make the equations look neater. Substituting $q = -\cot(\theta)$ into the second equation, we obtain:
$$
\dot r^2 + r^2 \dot \theta^2 = k^2 \csc^4(\theta) \dot\theta^2.
$$We also have that $\theta$ starts at $\frac{\pi}{4}$ with $r(\frac{\pi}{4}) = \sqrt{2}$, which is the point $(1,1)$, where the evil twin starts, and we continue until $\theta=\frac{3\pi}{4}$. Simplifying the ODE by solving for $\frac{\mathrm{d}r}{\mathrm{d}\theta}$, we obtain:
$\displaystyle
\left(\frac{\mathrm{d}r}{\mathrm{d}\theta}\right)^2 = k^2 \csc^4(\theta)-r^2, \quad\text{with } \theta \in \left[ \tfrac{\pi}{4}, \tfrac{3\pi}{4} \right],\quad r(\tfrac{\pi}{4}) = \sqrt{2}.
$
This ODE has everything we need to compute the trajectory of the evil twin. Note that the ODE does not actually depend on how fast we are moving (we have eliminated $p(t)$ and $t$ completely). Nevertheless, solving this is not so simple. There are two cases to consider:
- If $k^2 \csc^4(\theta) < r^2$, the right-hand side of the equation is negative, so there are no solutions! This happens when the evil twin is too far away from the lamppost and it becomes impossible for them to stay hidden because they cannot move fast enough.
- If $k^2 \csc^4(\theta) > r^2$, there are two possible values for $\frac{\mathrm{d}r}{\mathrm{d}\theta}$, which correspond to choosing either the positive or negative square root. In general, we don’t have to pick just one of them; we can make a different choice for each $\theta$, which yields infinitely many possible trajectories.
Since our goal is to finish with the largest possible $r$ (largest distance from the lamppost), one might suspect that we should pick the positive square root every time, so that $\frac{\mathrm{d}r}{\mathrm{d}\theta} > 0$. This greedy approach fails, however, because the evil twin gets too far from the lamppost too quickly, and ultimately gets stuck, unable to remain hidden behind the lamppost.
The ODE has no closed-form solution as far as I can tell, so I opted for a numerical/graphical approach. We can plot the slope field for the ODE, and we obtain the solution below:
We start at $(1,1)$, and at every location in space, we can follow the blue arrow or the orange arrow (either positive or negative square root), and we stop once we reach the finish line $y=-x$. The greedy solution (picking the positive square root the entire time) leads to a dead end, as the evil twin hits the infeasibility boundary (where blue and orange arrows coincide) and will no longer remain occluded by the lamppost. Along the line $y=2$ for $x\lt 0$, the blue lines are horizontal and the orange ones point downwards. So it is impossible to cross this boundary. Therefore, $(-2,2)$ is the farthest possible point from the lamppost achievable on the finish line, and we can achieve it by being greedy until we hit $y=0$, and then moving horizontally until we hit the finish line.
We conclude that the farthest distance is $2\sqrt{2}$, or about 282.84 feet, in the problem’s original units.
Generalizations
What happens if we vary $k$ (how much faster the evil twin is)?
- When $k < 1$, there is no solution; the evil twin can hide for a little while, but eventually, they will be revealed because they are simply not fast enough to remain hidden.
- When $k=1$, the optimal solution is for the evil twin to mirror perfectly, i.e. move horizontally and end at the point $(-1,1)$. Although it is possible to go farther from the lamppost initially, this leads to a dead end.
- When $1 \lt k \lessapprox 4.4$, the solution is similar to the one for $k=2$ derived above; the evil twin should be greedy until they reach the line $y=k$, then they should move horizontally until they reach the point $(-k,k)$, so the final distance from the lamppost is $k\sqrt{2}$.
- When $k\gtrapprox 4.4$, the evil twin is fast enough that being greedy the entire time pays off. However, the flow field in this case flattens out anyway, and we still end up at the same $(-k,k)$ optimal point, with a final distance of $k\sqrt{2}$.
Here is a figure showing minimal, subcritical, critical, and supercritical $k$.