calculus – Book Proofs

The weaving loom problem

This week’s Fiddler is a classic problem.

A weaving loom consists of equally spaced hooks along the x and y axes. A string connects the farthest hook on the x-axis to the nearest hook on the y-axis, and continues back and forth between the axes, always taking up the next available hook. This leads to a picture that looks like this:

As the number of hooks goes to infinity, what does the shape trace out?

Extra credit: If four looms are rotated and superimposed as shown below, what is the area of the white region in the middle?

My solution:
[Show Solution]

Suppose the weaving loom has size $1\times 1$. If a given string starts a fraction $\alpha$ away from the origin along the $y$-axis, so at the point $(0,\alpha)$, it will connect to the point $(1-\alpha,0)$ along the $x$-axis. Therefore, the set of all lines have equations:
\[
y = \alpha-\frac{\alpha}{1-\alpha}x
\]Suppose the limiting shape has equation $y = f(x)$. For a given $x$, $f(x)$ is the largest value of $y$ achievable for one of the lines above at that given $x$. This is illustrated in the diagram below:

In other words, we have:
\[
f(x) = \max_{0\leq\alpha\leq 1} \left( \alpha-\frac{\alpha}{1-\alpha}x \right)
\]It’s clear that the maximum will not occur at a boundary point ($\alpha=0$ or $\alpha=1$), so it must occur at a point where the derivative with respect to $\alpha$ is zero. In other words,
\[
\frac{\mathrm{d}}{\mathrm{d}\alpha}\left( \alpha-\frac{\alpha}{1-\alpha}x \right)
= 1-\frac{x}{(1-\alpha)^2} = 0
\]The optimal choice is $\alpha_\star = 1-\sqrt{x}$, and this leads to
\begin{align}
f(x) &= 1-\sqrt{x}-\frac{1-\sqrt{x}}{\sqrt{x}}x \\
&=1-2\sqrt{x}+x \\
&= (1-\sqrt{x})^2
\end{align}A more symmetric way to express this function is to write it implicitly. If $y=f(x)$, the set of points $(x,y)$ that satisfy the equation above are precisely the points that satisfy the equation

$\displaystyle
\sqrt{x} + \sqrt{y} = 1
$

Let’s dig a little deeper and see if we can learn more about the shape of this curve. Squaring both sides, rearranging, and squaring again, we obtain:
\[
x^2+y^2-2xy-2x-2y+1 = 0
\]This is a quadratic expression in $x$ and $y$, which means it is a conic section! So either a circle, ellipse, hyperbola, or parabola. But which one? The easiest way to check is to examine the eigenvalues of the quadratic part (there will be two eigenvalues). Here is a handy table for reference:
\[
\begin{array}{l|l}
\textbf{eigenvalue property} & \textbf{conic section} \\ \hline
\text{equal eigenvalues} & \text{circle} \\
\text{same sign and nonzero} & \text{ellipse} \\
\text{different sign and nonzero} & \text{hyperbola} \\
\text{one zero eigenvalue} & \text{parabola}
\end{array}
\]
In our case, the quadratic terms are:
\[
x^2+y^2-2xy = \begin{bmatrix}x\\y\end{bmatrix}^\mathsf{T}
\begin{bmatrix}1 & -1 \\ -1 & 1\end{bmatrix}
\begin{bmatrix}x\\y\end{bmatrix}
\]This matrix is singular (determinant is zero), so there is a zero eigenvalue, and the conic section must be a parabola! To make this more evident, we can rearrange the equation a bit more to obtain
\[
\left(\frac{x+y}{\sqrt{2}}\right) = \frac{1}{\sqrt{2}}\left(\frac{x-y}{\sqrt{2}}\right)^2 + \frac{1}{2\sqrt{2}}
\]If we imagine rotating our curve by $45$ degrees counterclockwise, this would correspond to the transformation $(x,y)\mapsto\left(\tfrac{x-y}{\sqrt{2}}, \tfrac{x+y}{\sqrt{2}} \right)$, so the equation above in rotated coordinates $(\hat x, \hat y)$ is simply
\[
\hat y = \frac{1}{\sqrt{2}}\hat x^2 + \frac{1}{2\sqrt{2}},
\]which is clearly a parabola.

Tangency. Based on the animation above, it looks like the line that crosses $(x,f(x))$ is also tangent to the curve at that point. To verify this, we can compute the derivative directly and compare it to the slope of the line:
\[
f'(x) = \frac{\mathrm{d}}{\mathrm{d}x}(1-\sqrt{x})^2 = 1-\frac{1}{\sqrt{x}}
\]But the $\alpha_\star$ we found for a point $x$ produces:
\[
\text{(slope of line)} = \frac{-\alpha_\star}{1-\alpha_\star} = \frac{-(1-\sqrt{x})}{1-(1-\sqrt{x})} = 1-\frac{1}{\sqrt{x}},
\]which is a perfect match!

Extra credit

To find the area of the central region, we can break our shape into pieces as shown below.

The point $x_0$ corresponds to the $x$-value of our curve where $y=\frac{1}{2}$. This is given by:
\[
x_0 = \left(1-\sqrt{\frac{1}{2}}\right)^2 = \frac{3}{2}-\sqrt{2} \approx 0.0858
\]The area of the central part is the total area of the square ($1$) minus four times the shaded area, which leads us to the integral:
\begin{align}
A &= 1-4\left( \frac{1}{2}x_0 + \int_{x_0}^{\frac{1}{2}} (1-\sqrt{x})^2\,\mathrm{d}x \right) \\
&= \frac{2}{3}\left(4\sqrt{2}-5\right) \\[2mm]
&\approx 0.4379
\end{align}I decided to spare you the details of the integration because they’re not particularly interesting. So the white area in the middle occupies approximately $43.8\%$ of the area of the square.

Making the fastest track

This week’s Riddler Classic is a problem about minimum-time optimization.

While passing the time at home one evening, you decide to set up a marble race course. No Teflon is spared, resulting in a track that is effectively frictionless. The start and end of the track are 1 meter apart, and both positions are 10 centimeters off the floor. It’s up to you to design a speedy track. But the track must always be at floor level or higher — please don’t dig a tunnel through your floorboards. What’s the fastest track you can design, and how long will it take the marble to complete the course?

My solution:
[Show Solution]

We will consider a more general version of the problem, where the start and end are $\ell$ meters apart, and the floor is $h$ meters below. Set up coordinates so the track starts at $(0,0)$ and ends at $(\ell,0)$, with the $y$-axis pointing downwards, so we have the constraint $y\leq h$.

If there were no floor to worry about, then the optimal path would be a brachistochrone curve. All minimum-time tracks have a path of this shape, which is given by the parametric equations
\begin{align}
x &= r(\theta-\sin\theta) \\
y &= r(1-\cos\theta)
\end{align}Here, $r$ is a parameter that is chosen depending on the location of the endpoint. Moreover, the marble will travel along this path in such a way that $\theta$ changes at a uniform rate. In particular, $\theta(t) = \sqrt{\frac{g}{r}} t$. In order to have the curve pass through $(\ell,0)$, we should pick $r = \frac{\ell}{2\pi}$. This produces the following result when $\ell=1$:

Unfortunately, this path has a maximum height of $y(\pi) = 2r = \frac{\ell}{\pi} \approx 0.31831$. So if the floor is any closer than this, the track will run into it. To deal with this situation, we will seek a design in three stages:

From $(0,0)$ to $(a,h)$ (moving down toward the floor).
From $(a,h)$ to $(\ell-a,h)$ (moving along the floor).
From $(\ell-a,h)$ to $(\ell,0)$ (moving back up to the endpoint).

We expect the solution to this problem to be symmetric, which is why we will assume the first and third segments of the path are mirror images of one another. Our task is to find $a$ and $r$ in order to minimize total time. Since the first segment is time-optimal, it must be a brachistochrone curve that passes through $(0,0)$ and $(a,h)$. Since it cannot dip below the floor, we must have $0\lt a \leq \frac{\pi h}{2}$ and since we must actually reach the floor, we must have $r \geq \frac{h}{2}$. Assuming it takes $\Delta T_1$ seconds to complete that portion of the path, we have
\begin{align}
a &= r(\theta-\sin \theta) \\
h &= r(1-\cos\theta) \\
\theta &= \sqrt{\frac{g}{r}} \Delta T_1
\end{align}Rearranging these equations, we can express $\theta,a,\Delta T_1$ in terms of $r$:
\begin{align}
\theta &= \arccos\left(1-\tfrac{h}{r}\right) \\
a &= r\left( \arccos\left(1-\tfrac{h}{r}\right)-\sqrt{1-(1-\tfrac{h}{r})^2} \right) \\
\Delta T_1 &= \sqrt{\frac{r}{g}}\arccos\left(1-\tfrac{h}{r}\right)
\end{align}

For the second portion of the path, the marble will travel at constant velocity $\sqrt{2gh}$ for a distance $\ell-2a$. So the total time $\Delta T_2$ for that portion satisfies
\[
\Delta T_2 = \frac{\ell-2a}{\sqrt{2gh}}
\]By symmetry, the third segment will take the same amount of time as the first one, so the total travel time is $\Delta T = 2\Delta T_1 + \Delta T_2$. Expressed in terms of $r$ alone, we get the complicated expression:
\begin{multline}
\Delta T = 2\sqrt{\frac{r}{g}}\arccos\left(1-\tfrac{h}{r}\right) \\
+ \frac{\ell-2r\left( \arccos\left(1-\tfrac{h}{r}\right)-\sqrt{1-(1-\tfrac{h}{r})^2} \right)}{\sqrt{2gh}}
\end{multline}Using calculus, we can verify that the first derivative of this expression with respect to $r$ is always positive. Therefore, the minimum value of $\Delta T$ occurs when $r$ is minimal. In other words, $r=\frac{h}{2}$. Substituting this in, we obtain the expression
\[
\frac{\ell+\pi h}{\sqrt{2 g h}}
\]Putting everything together, we can now write the complete solution to the problem. The minimum-time path has minimum time given by

$\displaystyle
\Delta T_\text{min} = \begin{cases}
\frac{\ell+\pi h}{\sqrt{2 g h}} & \text{if }0\lt h \leq \frac{\ell}{\pi} \\
\sqrt{\frac{2\pi \ell}{g}} & \text{if }h \gt \frac{\ell}{\pi}
\end{cases}
$

The second case corresponds to when the floor is far enough away that the fastest possible path (pure brachistocrone curve) does not touch the floor.

For the problem in question, we are told that $\ell=1$ and $h=0.1$ meters, so we are in the first case, and the minimum time is given by

$\displaystyle
\Delta T_\text{min}\text{ for $\ell=1$ and $h=0.1$ is }
\frac{1+0.1\pi}{\sqrt{2 g}} \approx 0.9382\,\text{sec.}
$

Here is what we get when we plot the time-optimal tracks for $\ell=1$ and several different values of $h$. The plot also includes the minimum times associated with each track.

If the floor is at height $h \leq \frac{\ell}{\pi}$ the equation of the first curved portion of the track follows the parametric equation from earlier, with $r=\frac{h}{2}$.
\[
\begin{aligned}
x &= \tfrac{h}{2}(\theta-\sin\theta)\\
y &= \tfrac{h}{2}(1-\cos\theta)
\end{aligned}
\qquad\theta\in[0,\pi]
\]The actual path traced out by the marble as a function of time is
\[
\begin{aligned}
x(t) &= \tfrac{h}{2}(\omega t-\sin\omega t)\\
y(t) &= \tfrac{h}{2}(1-\cos\omega t) \\
\omega &= \sqrt{\tfrac{2g}{h}} t
\end{aligned}
\qquad\text{with: }0\leq t \leq \tfrac{\pi\sqrt{h}}{\sqrt{2g}}
\]

I don’t have the technical skills required to make an animated gif of the marble moving along the curve at its appropriate speed, but the equations are above, so I’ll leave it up to somebody else!

Riddler Football Playoffs

This week’s Riddler Classic is a probability question inspired by the ongoing World Cup.

The Riddler Football Playoff (RFP) consists of four teams. Each team is assigned a random real number between 0 and 1, representing the “quality” of the team. If team $A$ has quality $a$ and team $B$ has quality $b$, then the probability that team $A$ will defeat team $B$ in a game is $\frac{a}{a+b}$.

In the semifinal games of the playoff, the team with the highest quality (the “1 seed”) plays the team with the lowest quality (the “4 seed”), while the other two teams play each other as well. The two teams that win their respective semifinal games then play each other in the final.

On average, what is the quality of the RFP champion?

My solution:
[Show Solution]

Suppose $a \gt b \gt c \gt d$. Consider the event that $A$ is the champion. In order for this to happen, $A$ must first defeat $D$ in the semifinals. Then, either $B$ wins their semifinal match and $A$ defeats $B$ in the finals, or $C$ wins their semifinal match and $A$ defeats $C$ in the finals. We can use a similar argument to compute the probability that $B$, $C$, or $D$ wins, and we obtain the following formulas:
\begin{align}
P_A &= \frac{a}{a+d}\left(\frac{b}{b+c}\cdot\frac{a}{a+b}+\frac{c}{b+c}\cdot\frac{a}{a+c}\right) \\
P_B &= \frac{b}{b+c}\left(\frac{a}{a+d}\cdot\frac{b}{a+b}+\frac{d}{a+d}\cdot\frac{b}{b+d}\right) \\
P_C &= \frac{c}{b+c}\left(\frac{a}{a+d}\cdot\frac{c}{a+c}+\frac{d}{a+d}\cdot\frac{c}{c+d}\right) \\
P_D &= \frac{d}{a+d}\left(\frac{b}{b+c}\cdot\frac{d}{b+d}+\frac{c}{b+c}\cdot\frac{d}{c+d}\right)
\end{align}One can check that $P_A+P_B+P_C+P_D=1$ for all values of $(a,b,c,d)$, since exactly one of these four outcomes must occur. The expected value of the quality of the champion is therefore
\[
x(a,b,c,d) = a P_A + b P_B + c P_C + d P_D.
\]Ultimately, we seek the average of $x(a,b,c,d)$ where each $a,b,c,d$ is chosen uniformly at random in $[0,1]$. The formulas above require $a\gt b \gt c \gt d$, but by symmetry each of the $4!=24$ permutations of $a,b,c,d$ is equally likely to occur. Therefore, we can restrict our averaging to the case where $a\gt b \gt c \gt d$ and multiply the result by $24$. This leads to the following formula for $\bar x$, the average value of $x$.
\[
\bar x = 24 \int_{a=0}^1 \int_{b=0}^a \int_{c=0}^b \int_{d=0}^c x(a,b,c,d)\,
\mathrm{d}d\,\mathrm{d}c\,\mathrm{d}b\,\mathrm{d}a
\]This integral is very difficult to evaluate by hand, so I used Mathematica, and found the result to be:
\begin{align}
\bar x
&= \frac{2}{5} \left(23-(29+2\pi^2)\log(2)+39\log^2(2)-8\log^3(2)-3\zeta(3)\right)\\
&\approx 0.6735417813867959221089
\end{align}Here, $\zeta$ is the Riemann zeta function. The constant $\zeta(3)=\sum_{n=1}^\infty\frac{1}{n^3}\approx 1.2020569$ is known as Apéry’s constant. The reason this constant shows up is because we are repeatedly integrating products of rational functions, and it turns out that
\[
\zeta(3) = \int_0^1\int_0^1\int_0^1\frac{1}{1-xyz}\,\mathrm{d}x\,\mathrm{d}y\,\mathrm{d}z
\]Fun fact: it is known that $\zeta(3)$ is irrational, but it is still not known whether it is transcendental!

Numerical verification

I also obtained an estimate for $\bar x$ by performing a Monte Carlo simulation of 10 million games of Riddler Football Playoff in Matlab. Here is my code:

N = 1e7;

quality = zeros(N,1);
for trial = 1:N
   
    x = sort(rand(4,1));
    a = x(4); b = x(3); c = x(2); d = x(1);
    
    % F = winner of Semifinal 1 (A vs D)
    if rand < a/(a+d)
        f = a;
    else
        f = d;
    end
    
    % G = winner of Semifinal 2 (B vs C)
    if rand < b/(b+c)
        g = b;
    else
        g = c;
    end
    
    % X = winner of Finals (F vs G)
    if rand < f/(f+g)
        quality(trial) = f;
    else
        quality(trial) = g;
    end
end
avg = mean(quality)
sem = std(quality)/sqrt(N);
conf_interval = [avg-1.96*sem,avg+1.96*sem]

Running the code above took about 10 seconds and produced an estimate of $0.67353$, with a 95% confidence interval $[0.67339, 0.67367]$. So it looks like there is good agreement between the numerical value derived from the exact formula and the empirical Monte Carlo estimate.

Randomly cutting a sandwich

This week’s Riddler Classic is geometry puzzle about randomly slicing a square sandwich.

I have made a square sandwich, and now it’s time to slice it. But rather than making a standard horizontal or diagonal cut, I instead pick two random points along the perimeter of the sandwich and make a straight cut from one point to the other. (These points can be on the same side.)

What is the probability that the smaller resulting piece has an area that is at least one-quarter of the whole area?

My solution:
[Show Solution]

Suppose the sandwich has side length 1. Let $t \in [0,1]$ be location of the first point (measured from a corner). We have three cases to consider:

If the second point is on the same side (probability $\frac{1}{4}$), the area of the resulting smallest piece will be zero.
If the second point is on an adjacent side (probability $\frac{1}{2}$), the area of the resulting smallest piece will be $\frac{1}{2}tr$, where $r \in [0,1]$ is the location of the second point on the adjacent side.
If the second point is on the opposite side (probability $\frac{1}{4}$), the area of the resulting piece will be the smaller of the two resulting quadrilaterals. Specifically, it will be $\min(\frac{t+r}{2},1-\frac{t+r}{2})$, where $r \in [0,1]$ is the location of the second point on the opposite side.

We will solve the general case, which is to find the probability that the smallest slice will have a fraction at least $p$ of the total area. the problem asks for $p=\frac{1}{4}$. Since the total area of the square is $1$, we are effectively asking: “what is the probability that the smallest area is at least $p$?”.

Case 1. If we are in the first case (points on the same side), the probability that the area is greater than $p$ is zero, since the area is always zero. So we conclude that:
\[
a_1 = 0
\]

Case 2. If we are in the second case (points on an adjacent sides), we want the probability that $\frac{1}{2}tr > p$, where $r$ and $t$ are chosen uniformly at random in $[0,1]$. This amounts to computing:
\begin{align}
a_2 &= \int_0^1 \int_0^1 \mathbf{1}\bigl( \tfrac{1}{2}tr \gt p \bigr)\,\mathrm{d}r\,\mathrm{d}t \\
&= \int_{2p}^1 \int_0^1 \mathbf{1}\bigl(r \gt \tfrac{2p}{t} \bigr)\,\mathrm{d}r\,\mathrm{d}t \\
&= \int_{2p}^1 \left( 1-\frac{2p}{t}\right)\,\mathrm{d}t \\
&= 1-2p+2p\log(2p)
\end{align}Note that we had to change the lower bound of the integral for $t$ because when $t \lt 2p$, we have $\tfrac{2p}{t}\gt 1$, so the integrand is zero. Geometrically, this is the fraction of the region $(t,r)\in[0,1]^2$ where $tr\gt p^2$, sketched below.

Case 3. If we are in the third case (points on opposite sides), we perform a similar computation with the area of the quadrilateral:
\begin{align}
a_3 &= \int_0^1 \int_0^1 \mathbf{1}\bigl( \min(\tfrac{t+r}{2},1-\tfrac{t+r}{2}) \gt p \bigr)\,\mathrm{d}r\,\mathrm{d}t \\
&= \int_0^1 \int_0^1 \mathbf{1}\bigl( \tfrac{t+r}{2}\gt p\text{ and } 1-\tfrac{t+r}{2} \gt p \bigr) \,\mathrm{d}r\,\mathrm{d}t \\
&= \int_0^1 \int_0^1 \mathbf{1}\bigl( p \lt \tfrac{t+r}{2} \lt 1-p\bigr) \,\mathrm{d}r\,\mathrm{d}t \\
&= \int_0^1 \int_0^1 \mathbf{1}\bigl( 2p \lt t+r \lt 2-2p\bigr) \,\mathrm{d}r\,\mathrm{d}t \\
&= 1-4p^2
\end{align}A trick to evaluating the above integral is to do it geometrically. Sketching the region for which $2p\lt t+r\lt 2-2p$, we see that it is the square of area $1$ with the two corners cut off, whose area is $(2p)^2$, so the result is $1-4p^2$. See below for an illustration.

Putting everything together, the probability that the area of the smallest piece is at least $p$ is given by sum of the probabilities we already calculated, each weighted by their likelihood of occurrence, so $f(p) = \frac{1}{4}a_1 + \frac{1}{2}a_2 + \frac{1}{4}a_3$. Plugging in the results from above and simplifying, we obtain our final answer:

$\displaystyle
f(p) = \frac{3}{4}-p-p^2+p \log (2 p)
$

Here is what the function looks like:

Naturally, the plot only extends to $p=\frac{1}{2}$ because the area of the smaller piece cannot be more than half of the total area. When $p=\frac{1}{4}$ (what the original problem asked about), we obtain $f(\frac{1}{4}) = \frac{7}{16}-\frac{\log (2)}{4}\approx 0.264213$. So the probability that the smaller piece is at least one quarter of the whole area is about 26.4%.

Fall color peak

This week’s Riddler Classic is a seasonal puzzle about leaves changing color.

The trees change color in a rather particular way. Each tree independently begins changing color at a random time between the autumnal equinox and the winter solstice. Then, at a random later time for each tree — between when that tree’s leaves began changing color and the winter solstice — the leaves of that tree will all fall off at once. At a certain time of year, the fraction of trees with changing leaves will peak. What is this maximal fraction?

My solution:
[Show Solution]

Another way to solve the problem, courtesy of Matthew Wallace:
[Show Solution]

Catch the grasshopper

This week’s Riddler classic is a probability problem about a grasshopper!

You are trying to catch a grasshopper on a balance beam that is 1 meter long. Every time you try to catch it, it jumps to a random point along the interval between 20 centimeters left of its current position and 20 centimeters right of its current position. If the grasshopper is within 20 centimeters of one of the edges, it will not jump off the edge. For example, if it is 10 centimeters from the left edge of the beam, then it will randomly jump to anywhere within 30 centimeters of that edge with equal probability (meaning it will be twice as likely to jump right as it is to jump left). After many, many failed attempts to catch the grasshopper, where is it most likely to be on the beam? Where is it least likely? And what is the ratio between these respective probabilities?

My solution:
[Show Solution]

Let’s suppose the beam has length $L$ and the grasshopper can jump a maximum distance $\frac{M}{2}$. Define $p(x)$ to be the probability density function describing how likely the grasshopper is to be at any given location $x\in\left[-\frac{L}{2},\frac{L}{2}\right]$.

We can arrive at $p(x)$ via a sequential process. Suppose that at time $k$, the grasshopper has distribution $p_k(x)$. When the grasshopper jumps, its probability distribution becomes $p_{k+1}(x)$. Our goal is to find the limiting distribution $p = \lim_{k\to\infty} p_k$.

At each step, the grasshopper’s density function gets convolved with an appropriate uniform distribution corresponding with where it might land. We can write this as:
\[
p_{k+1}(x) = \int_{-L/2}^{L/2} \Psi(x,y) p_k(y) \,\mathrm{d}y.
\]Here, for each $y$, the kernel $\Psi(x,y)$ is the density function (of $x$) corresponding to a uniform distribution between $\max\bigl(-\frac{L}{2},y-\frac{M}{2}\bigr)$ and $\min\bigl(\frac{L}{2},y+\frac{M}{2}\bigr)$, since this corresponds to the range of locations a grasshopper at location $y$ can jump to. Putting all this together, we get the formula:
\[
p_{k+1}(x) = \int_{\max\bigl(-\frac{L}{2},x-\frac{M}{2}\bigr)}^{\min\bigl(\frac{L}{2},x+\frac{M}{2}\bigr)} \frac{p_k(y)\,\mathrm{d}y}{\min\bigl(\frac{L}{2},y+\frac{M}{2}\bigr)-\max\bigl(-\frac{L}{2},y-\frac{M}{2}\bigr)}.
\]Yuck! To get a better handle on what this might look like, we can simulate it using the given problem parameters ($L=1$ and $M=0.4$) using units of meters. Here is what we obtain when recursively apply the above formula, assuming $p_0$ is a uniform distribution:

The steady-state distribution is the same no matter what we use as the starting distribution. Here is what it looks like when we start the grasshopper on the left edge of the beam. I had to use different axis scaling to make the transient behavior fit in the plot, but the limiting distribution in the same:

These simulations give us a big hint: The limiting distribution appears to be piecewise-linear! We already expected a symmetric distribution due to the symmetry in the problem, but now we can posit a density function of the form:
\[
p(x) = \begin{cases}
ax+b & -\frac{L}{2}\leq x \leq -\left|\frac{L-M}{2}\right| \\
c & -\left|\frac{L-M}{2}\right| < x < \left|\frac{L-M}{2}\right| \\ -ax+b & \left|\frac{L-M}{2}\right| \leq x \leq \frac{L}{2} \end{cases} \]We have three unknown parameters $(a,b,c)$, so we need three equations. First, $p$ is a probability density, so $\int_{-L/2}^{L/2}p(x)\,\mathrm{d}x=1$. Second, $p$ is continuous at the boundaries $x=\pm \left|\frac{L-M}{2}\right|$. Finally, we must satisfy $p(x) = p_{k+1}(x) = p_k(x)$ in the original recursion in our original recursion. Solving these equations, we find three cases: \[ p(x) = \begin{cases} \begin{cases} \frac{2 (L+M+2 x)}{M (4 L-M)} & -\frac{L}{2}\leq x \leq \frac{-L+M}{2} \\ \frac{4}{4 L-M} & \frac{-L+M}{2} < x < \frac{L-M}{2} \\ \frac{2 (L+M-2 x)}{M (4 L-M)} & \frac{L-M}{2} \leq x \leq \frac{L}{2} \end{cases} & 0 < M < L \\[3mm] \begin{cases} \frac{2 (L+M+2 x)}{M (4 L-M)} & -\frac{L}{2}\leq x \leq \frac{-M+L}{2} \\ \frac{4 L}{M (4 L-M)} & \frac{-M+L}{2} < x < \frac{M-L}{2} \\ \frac{2 (L+M-2 x)}{M (4 L-M)} & \frac{M-L}{2} \leq x \leq \frac{L}{2} \end{cases} & L < M < 2L \\[3mm] \quad\frac{1}{L} & 2L < M \end{cases} \] We can also calculate the ratio of largest to smallest likelihood in all three cases. The largest likelihood occurs in the center ($x=0$) while the smallest occurs at an edge ($x=\pm\frac{L}{2}$). We then obtain: \[ \frac{p_\text{max}}{p_\text{min}} = \begin{cases} 2 & 0 < M < L \\[1mm] \frac{2L}{M} & L < M < 2L \\[1mm] 1 & 2L < M \end{cases} \] So, amazingly, the ratio of largest likelihood to the smallest likelihood is 2, a constant indepedent of the length $L$ or the grasshopper range $M$, so long as $M < L$. In particular, the likelihood ratio is $2$ for the setting given in the problem statement ($L=1$ and $M=0.4$).

Cone crawling

This week’s Riddler Classic is a geometry problem about traversing the surface of a cone

The circular base of the cone has a radius of 2 meters and a slant height of 4 meters. We start on the base, a distance of 1 meter away from the center. The goal is to reach the point half-way up the cone, 90 degrees around the cone’s central axis from the start, as shown. What is the shortest path?

Here is my solution:
[Show Solution]

Suppose the base has radius $r_0$ and we start a distance $\rho_0$ from the center (point $A$). Suppose the slant height is $r_1$ and our goal is to reach a point $\rho_1$ from the top (point $B$). We can break the journey into two parts. No matter how we get from $A$ to $B$, we must reach the edge of the base (point $X$) at some point on our journey. Suppose $X$ is located at an angle $\theta$ from the center of the base.

In the diagram above, we show the 3D cone and the corresponding unfolded 2D version to the right. The corresponding points have matching labels (click the diagram to enlarge) The first part of the journey, from $A$ to $X$, should be a straight line, since this is the shortest distance connecting two points on a flat surface. By the law of cosines, the distance $AX$ is
\[
|AX| = \sqrt{ r_0^2 + \rho_0^2-2r_0\rho_0\cos(\theta) }
\]The second part of the journey, from $X$ to $B$, will be a curved path along the surface of the cone. However, since we want the shortest possible path, this will be a straight line if we unfold the cone. This unfolded cone is a circular sector with radius $r_1$. Based on the diagram below, we can apply the law of cosines again to find the distance $XB$:
\[
|XB| = \sqrt{ r_1^2 + \rho_1^2-2r_1\rho_1\cos(\phi) }
\]But what is $\phi$? The arclengths along the edge of the base for both parts of the path must sum to 90 degrees. So the sum of both arclengths must equal one quarter of the circumference of the base. In other words, the points $X’$ and $R’$ must coincide with $X$ and $R$, respectively, when we fold the cone back together. Therefore,
\[
r_0 \theta + r_1 \phi = \tfrac{\pi}{2}r_0
\]Putting these three ingredients together, our goal is to solve the optimization problem:
\begin{align}
\underset{\theta,\phi}{\text{minimize}} \quad & \sqrt{ r_0^2 + \rho_0^2-2r_0\rho_0\cos(\theta) } + \sqrt{ r_1^2 + \rho_1^2-2r_1\rho_1\cos(\phi) } \\
\text{subject to} \quad & r_0 \theta + r_1 \phi = \tfrac{\pi}{2}r_0 \\
& 0 \leq \theta \leq \tfrac{\pi}{2}
\end{align}

Eliminating $\phi$ from the objective, we can write a single expression for the total distance $f(\theta)$ traveled in terms of the location $\theta$ of the crossover point:
\[
f(\theta) = \sqrt{ r_0^2 + \rho_0^2-2r_0\rho_0\cos(\theta) }
+ \sqrt{ r_1^2 + \rho_1^2-2r_1\rho_1\cos\Bigl[\tfrac{r_0}{r_1}\bigl(\tfrac{\pi}{2}-\theta\bigr)\Bigr] }
\]Here is a plot of what this function looks like when we use the parameters given in the problem statement ($r_0=2$, $\rho_0=1$, $r_1=4$, $\rho_1=2$)

We can see the minimum occurs at around 30 degrees. Next, we will dig a bit deeper and show that the minimum occurs at exactly 30 degrees, and we will derive a solution in the more general case.

General solution

For general values of $(r_0,\rho_0,r_1,\rho_1)$, we can look for a value of $\theta$ that minimizes $f(\theta)$ by taking the derivative and setting it equal to zero. However, the algebra is a bit simpler if we do not eliminate $\phi$ and write down optimality conditions using the method of Lagrange multipliers. Doing this and simplifying, we obtain two conditions:
\begin{gather}
\frac{\rho_0\sin\theta}{\sqrt{ r_0^2+\rho_0^2-2 r_0 \rho_0\cos(\theta)}}
= \frac{\rho_0\sin\phi}{\sqrt{ r_1^2+\rho_1^2-2 r_1 \rho_1\cos(\phi)}}
\\
\theta + \frac{r_1}{r_0} \phi = \frac{\pi}{2}
\end{gather}By the law of sines, the first equation says that $\alpha = \angle OXA = \angle PX’B$. Intuitively, this has the following interpretation: If we imagine rolling one circle around the other until points $X$ and $X’$ coincide, the points $B,X’,X,O$ will all lie on a straight line (the two red segments form a straight line). By writing out the law of sines on the third side, we can obtain slightly simpler expressions now involving $(\theta,\phi,\alpha)$:
\begin{align}
\rho_0 \sin(\theta+\alpha) &= r_0 \sin(\alpha) \\
\rho_1 \sin(\phi+\alpha) &= r_1 \sin(\alpha) \\
\theta + \tfrac{r_1}{r_0}\phi &= \tfrac{\pi}{2}
\end{align}Expanding the first two equations using angle sum identities and eliminating $\alpha$, we obtain an even simpler set of equations:
\[
\frac{\tfrac{r_0}{\rho_0}-\cos\theta}{\sin\theta} = \frac{\tfrac{r_1}{\rho_1}-\cos\phi}{\sin\phi}
\quad\text{and}\quad
\theta + \tfrac{r_1}{r_0}\phi = \tfrac{\pi}{2}
\]This is pretty difficult to solve in general, but certain special cases make things easier. For example, if $\tfrac{r_0}{\rho_0}=\tfrac{r_1}{\rho_1}$, then we must have $\theta=\phi$. This is precisely the case in the problem statement, because we have $\tfrac{r_0}{\rho_0}=\tfrac{r_1}{\rho_1}=2$. Furthermore, we have $\tfrac{r_1}{r_0}=2$, so the second condition becomes $\theta + 2\theta = \tfrac{\pi}{2}$, from which we conclude that $\theta=\tfrac{\pi}{6}=30^\circ$. Substituting back into the formula for total distance, we find the length of the shortest path:

$\displaystyle
\text{Minimum distance} = f\bigl(\tfrac{\pi}{6}\bigr) = 3 \sqrt{5-2 \sqrt{3}} \approx 3.71794
$

So we can find an analytic solution to this problem whenever the start and end points are the same fraction of the way from the centers of their respective circles!

The luckiest coin

This week’s Riddler Classic is about finding the “luckiest” coin!

I have in my possession 1 million fair coins. I first flip all 1 million coins simultaneously, discarding any coins that come up tails. I flip all the coins that come up heads a second time, and I again discard any of these coins that come up tails. I repeat this process, over and over again. If at any point I am left with one coin, I declare that to be the “luckiest” coin.

But getting to one coin is no sure thing. For example, I might find myself with two coins, flip both of them and have both come up tails. Then I would have zero coins, never having had exactly one coin.

What is the probability that I will at some point have exactly one “luckiest” coin?

Here is my solution:
[Show Solution]

Let’s define $p_n$ to be the probability that we will end up with exactly one “luckiest” coin, given that we start with $n$ coins. Our terminal conditions are that $p_0=0$ and $p_1=1$, since we lose if we end up with zero and we win if we end up with one. We can define the rest of the $p_n$ recursively as follows. If we flip the $n$ coins and obtain $k$ heads, then the probability we will win is $p_k$. The probability of obtaining $k$ heads is $\binom{n}{k}\frac{1}{2^n}$. Therefore,
\[
p_n = \sum_{k=0}^n \frac{1}{2^n} \binom{n}{k} p_k\qquad\text{for }n=2,3,\dots
\]Note that $p_n$ appears on both sides of the equation, since it’s possible that we flip all Heads, and we remain with $n$ coins at the next turn. We can solve for $p_n$ by rearranging the equation, and we obtain the complete recursion:

$\displaystyle
\begin{aligned}
p_0&=1,\quad p_1=1,\\
p_n &= \frac{1}{2^n-1} \sum_{k=0}^{n-1}\binom{n}{k} p_k\qquad\text{for }n=2,3,\dots
\end{aligned}
$

Let’s start with a simple simulation to see what we’re dealing with. Here is what we get for $n$ up to 50:

Seems like we’re done! The sequences appears to settle quickly. A numerical evaluation shows the limit to be approximately 0.72135, or 72.1%.

Down the rabbit hole

Appearances can be deceiving! First, we can expect the number of coins to roughly drop by a factor of 2 at each turn, so we should expect that $p_n \approx p_{2n}$ for large $n$. This suggests that we should plot $n$ on a log scale. Let’s see what happens if we make the same plot as before, except this time go up to $2^{12} = 4{,}096$, and we ignore the initial large swings in values to just focus on the tail end.

Would you look at that! The plot tends to a sinusoid. And although the amplitude decays rapidly at first, it does not decay to zero! If you have been following the Riddler for some time, this may seem familiar to you. In fact, a very similar pattern of decaying sinusoids on a log scale that don’t quite decay to zero was observed in the puzzle of The lonesome king, published about five and a half years ago!

It might be possible to actually compute all the way up to $10^6$, but it would likely take quite awhile (on my laptop, anyway). Computing up to $n=5000$ already took over one minute. And the scaling is not linear! Computing each $p_n$ involves all previous $p_k$, so the computation scales like $n^2$. Moreover, the binomial coefficients become so large that computing them exactly would take a lot of time and memory, and approximating them would further complicate the solution.

To approximate the probability when $n=10^6$, the easiest way is to leverage the periodicity of the function and reduce the quantity of interest to one that is within the range of values we have already computed. We have that:
\[
p_{10^6} = p_{10^6/2^8} \approx p_{3096} \approx 0.72134685.
\]Granted, the limiting amplitude of the sinusoid is so small that even if we use our original guess of 0.72135, we will be correct to 5 decimal places for any $n$ sufficiently large. So at the end of the day, we don’t gain much by doing all this extra work.

As with the Lonesome King puzzle, we are once again faced with this puzzling phenomenon of marginally stable oscillations. There are several questions that seem natural to ask:

Is there a closed-form expression for the limiting amplitude?
Is there a closed-form expression for the limiting mean?
Is the limiting waveform actually a true sinusoid?

To answer these questions, we have to go deeper…

Deeper down the rabbit hole

After more thought (and many great comments here and on Twitter), I decided to take another crack at the problem. I started with the approach used by Allen Gu, where he derived a non-recursive formula for $p_n$:
\[
p_n = \frac{n}{2}\sum_{t=0}^\infty 2^{-t} \left( 1-2^{-t} \right)^{n-1}
\]Define the inside function as
\[
g_n(t) = \frac{n}{2}2^{-t} \left( 1-2^{-t} \right)^{n-1}
\]Here is what $g_n(t)$ looks like for different values of $n$:

It appears that $g_n(t)$ gets shifted to the right as we increase $n$. The height and width of the peak appears to remain constant. To confirm this mathematically, we can solve $\frac{\mathrm{d}}{\mathrm{d}t}g_n(t) = 0$ and we find that the peak occurs at $t = \log_2(n)$. Since our plan is to sum $g_n(t)$ over all $t$ anyway, then we might as well shift it so that it is centered at its peak. If the offset from the peak is $\tau$, then the shifted function is:
\begin{align}
h_n(\tau) &= g_n(\log_2(n) + \tau) \\
&= 2^{-\tau-1} \left(1-\frac{2^{-\tau}}{n}\right)^{n-1}
\end{align}We can evaluate the limit as $n\to\infty$, and we see that:
\[
h(\tau) = \lim_{n\to\infty}h_n(\tau) = 2^{-\tau-1} e^{-2^{-\tau}}
\]It follows that in the limit of large $n$, the probability $p_n$ will take on all values in the range
\[
p(x) = \sum_{\tau=-\infty}^\infty 2^{-\tau-1+x} e^{-2^{-\tau+x}}\quad\text{for }x\in[0,1]
\]Of course, due to the translation invariance of the sum, this must be a periodic function. Here is what it looks like:

It looks very close to a sinusoid. However, it is not. If it were a true sinusoid, then $p(x)+p(x+\tfrac{1}{2})$ would be constant for all $x$. We can verify that this is not the case by doing an accurate numerical evaluation of the sums for two different values of $x$. We find:
\begin{align}
\tfrac{1}{2}(p(0.3)+p(0.8)) &\approx 0.72134752045108504298 \\
\tfrac{1}{2}(p(0.5)+p(1.0)) &\approx 0.72134752043912493759
\end{align}So they differ in the $11^\text{th}$ decimal digit.

Given that the function $p(x)$ is not a true sinusoid, we have to re-examine what we mean by “limiting value”. One way to define this would be the average value over one period. Thankfully, this integral can be evaluated exactly, and we obtain:
\begin{align}
\int_0^1 p(x)\,\mathrm{d}x &= \int_0^1 \sum_{\tau=-\infty}^\infty 2^{-\tau+x-1} e^{-2^{-\tau+x}}\,\mathrm{d}x \\
&= \sum_{\tau=-\infty}^\infty \int_0^1 2^{-\tau+x-1} e^{-2^{-\tau+x}}\,\mathrm{d}x \\
&= \sum_{\tau=-\infty}^\infty \frac{e^{2^{-\tau}}-e^{-2^{-(\tau-1)}}}{2\log (2)} \\
&= \lim_{M,N\to\infty} \sum_{\tau=-N}^M \frac{e^{2^{-\tau}}-e^{-2^{-(\tau-1)}}}{2\log (2)} \\
&= \frac{1}{2\log(2)} \left[ \lim_{M\to\infty} e^{-2^{-M}}-\lim_{N\to\infty}e^{-2^{N+1}} \right]\\
&= \frac{1}{2\log(2)}
\end{align}The bi-infinite sum is actually a telescoping series, which is pretty nice!

In conclusion, we showed that the limiting function is periodic (peak-to-peak is about $1.4\times 10^{-5}$), it is not a true sinusoid (but very close), and its mean value is exactly $\frac{1}{2\log(2)}$.

Rabbits all the way down

Our previous expression for the limiting distribution was:
\[
p(x) = \sum_{\tau=-\infty}^\infty 2^{-\tau+x-1} e^{-2^{-\tau+x}}\quad\text{for }x\in[0,1]
\]This is a periodic function, so why not find its Fourier series? To refresh your memory, since $p(x)$ is periodic with period $1$, we can write
\[
p(x) = \sum_{n=-\infty}^\infty c_n e^{2\pi i n x},\quad\text{where:}\quad
c_n = \int_0^1 p(x) e^{-2\pi i n x}\,\mathrm{d}x
\]Amazingly, we can evaluate $c_n$ in (somewhat) closed form:
\begin{align}
c_n &= \int_0^1 p(x) e^{-2\pi i n x} \\
&= \int_0^1 \sum_{\tau=-\infty}^\infty 2^{-\tau+x-1} e^{-2^{-\tau+x}} e^{-2\pi i n x}\,\mathrm{d}x \\
&= \sum_{\tau=-\infty}^\infty \int_0^1 2^{-\tau+x-1} e^{-2^{-\tau+x}} e^{-2\pi i n x}\,\mathrm{d}x
\end{align}Substitute $u = 2^{-\tau+x}$, so $\mathrm{d}u = u\log(2) \mathrm{d}x$, and $x=\tau+\log_2(u)$:
\begin{align}
c_n &= \sum_{\tau=-\infty}^\infty \frac{1}{2\log(2)}\int_{2^{-\tau}}^{2^{-\tau+1}} e^{-u}e^{-2\pi in(\tau+\log_2(u))}\,\mathrm{d}u \\
&= \frac{1}{2\log(2)} \sum_{\tau=-\infty}^\infty \int_{2^{-\tau}}^{2^{-\tau+1}} e^{-u}u^{-2\pi in/\log(2)}\,\mathrm{d}u \\
&= \frac{1}{2\log(2)} \int_{0}^{\infty} e^{-u}u^{-2\pi i n/\log(2)}\,\mathrm{d}u \\
&= \frac{\Gamma\bigl(1-\tfrac{2\pi i n}{\log(2)}\bigr)}{2\log(2)},
\end{align}where $\Gamma(z)$ is the gamma function. Therefore, the Fourier series of $p(x)$ is
\[
p(x) = \sum_{n=-\infty}^\infty \frac{\Gamma\bigl(1-\tfrac{2\pi i n}{\log(2)}\bigr)}{2\log(2)} e^{2\pi i n x}
\]Define $\alpha_n := \Gamma\bigl(1-\tfrac{2\pi i n}{\log(2)}\bigr) = |\alpha_n|e^{i \arg(\alpha_n)}$, and we can write the series in a more familiar way using standard trig functions:
\[
p(x) = \frac{1}{2\log(2)} + \frac{1}{\log(2)}\sum_{n=1}^\infty |\alpha_n| \cos\bigl( 2\pi n x+\arg(\alpha_n) \bigr)
\]There is actually a closed-form expression for the magnitude of the gamma function when the real part of the argument is an integer (see here). Specifically, we have $|\Gamma(1+ib)|^2 = \frac{\pi b}{\sinh(\pi b)}$ for all $b\in \mathbb{R}$. Therefore, we can write the Fourier series for $p(x)$ as:
\[
p(x) = \frac{1}{2\log(2)} + \sum_{n=1}^\infty \sqrt{ \frac{2 \pi^2 n \,\text{csch}\bigl(\tfrac{2 \pi ^2 n}{\log (2)}\bigr)}{\log^{3}(2)}
} \cos\bigl( 2\pi n x + \arg(\alpha_n) \bigr)
\]where $\text{csch}(z) := \frac{2}{e^z-e^{-z}}$ is the hyperbolic cosecant. The Fourier coefficients $|\alpha_n|$ decrease very rapidly with increasing $n$. In fact, we have:
\begin{align}
c_n &= \sqrt{ \frac{2 \pi^2 n \,\text{csch}\bigl(\tfrac{2 \pi ^2 n}{\log (2)}\bigr)}{\log^{3}(2)}} \\
c_1 &\approx 7.1301\times 10^{-6} \\
c_2 &\approx 6.60339\times 10^{-12} \\
c_3 &\approx 5.29624\times 10^{-18} \\
\end{align}As we increase $n$, we have $c_n \sim \exp\bigl(-\tfrac{n \pi^2}{\log(2)}\bigr) \approx 10^{-6.184 n}$. This is why the amplitude of $p(x)$ is so small, and why it looks so close to being a sinusoid when we plot it.

Using this information, we can return to the original problem and write out an exact expression for the steady-state function in terms of the original $n$ (number of coins). This yields the expression:
\[
p_n \to \frac{1}{2\log(2)} + \sum_{k=1}^\infty \sqrt{ \frac{2 \pi^2 k \,\text{csch}\bigl(\tfrac{2 \pi ^2 k}{\log (2)}\bigr)}{\log^{3}(2)}
} \cos\Bigl( 2\pi k \log_2(n) + \arg \Gamma\bigl(1-\tfrac{2\pi i k}{\log(2)}\bigr) \Bigr)
\]

The first few terms of the series are:
\begin{multline}
p_n \approx 0.72134752044448170368 \\
+ \left(7.130117\times 10^{-6}\right) \cos\bigl( 2\pi \log_2(n) +0.872711\bigr) \\
+ \left(6.603386\times 10^{-12}\right) \cos\bigl( 4\pi \log_2(n) +2.51702\bigr) + \dots
\end{multline}

Finally, here is the numerical data overlaid with the first harmonic approximation (only keeping the first term of the sum). Looks pretty good!

Equipped with this series, we can now evaluate the probability of finding a “luckiest coin” when there are $n=10^6$ coins. Here is a very accurate approximation (all digits significant)
\[
p_{1,000,000} \approx 0.7213539630726652117823954768
\]

Triangle Trek

This week’s Riddler Classic is a problem involving traversing a triangle.

Amare the ant is traveling within Triangle ABC, as shown below. Angle A measures 15 degrees, and sides AB and AC both have length 1.

Amare must:

Start at point B.
Second, touch a point — any point — on side AC.
Third, touch a point — any point — back on side AB.
Finally, proceed to a point — any point — on side AC (not necessarily the same point he touched earlier).

What is the shortest distance Amare can travel to complete the desired path?

I solved the problem in two different ways. The elegant solution:
[Show Solution]

And the more complicated solution:
[Show Solution]

We can also use calculus to solve the problem. Let’s start with the same picture as before:

Suppose $|AD|=x$, $|AE|=y$, and $|AF|=z$. From the law of cosines:
\begin{align}
|BD| &= \sqrt{1+x^2-2x\cos(\theta)} \\
|DE| &= \sqrt{x^2+y^2-2xy\cos(\theta)} \\
|EF| &= \sqrt{y^2+z^2-2yz\cos(\theta)}
\end{align}Let $f(x,y,z)$ be the sum of these three distances, which is the total distance traveled by Amare. We want to find $x,y,z$ such that $f(x,y,z)$ is minimized. A necessary condition for minimality is that the partial derivatives of $f$ with respect to $x,y,z$ should be zero. Let’s start with $z$:
\[
\frac{\partial}{\partial z}f(x,y,z) = \frac{z-y \cos (\theta )}{\sqrt{y^2+z^2-2 y z \cos (\theta )}}
\]Setting this equal to zero, we conclude that $z=y\cos(\theta)$. We can now substitute this value of $z$ into the definition for $f$ and we obtain a simpler expression in only two variables:
\begin{align}
g(x,y) &= f(x,y,y\cos(\theta)) \\
&= \sqrt{1+x^2-2x\cos(\theta)} + \sqrt{x^2+y^2-2xy\cos(\theta)} + y\sin(\theta)
\end{align}To make sure there is no funny business going on, let’s plot this function to see what it looks like for $\theta=15^\circ$. Here is a contour plot:

We can clearly see that there is a unique minimum that occurs in the region near $(x,y) \approx (0.8,0.7)$. Ok, so let’s proceed. Consider now the derivative with respect to $y$:
\[
\frac{\partial}{\partial y} g(x,y) = \frac{y-x \cos (\theta )}{\sqrt{x^2+y^2-2 x y \cos (\theta )}} + \sin (\theta )
\]Setting this equal to zero (I’ll spare you the algebra), we obtain $y = x \cos(2\theta)\sec(\theta)$. Substituting this into $g(x,y)$, we obtain a function of just $x$:
\begin{align}
h(x) &= g(x,x \cos(2\theta)\sec(\theta)) \\
&= \sqrt{1+x^2-2 x \cos (\theta )}+x \sin (2 \theta )
\end{align}Finally, we can take the derivative with respect to $x$:
\[
\frac{\partial}{\partial x}h(x) = \frac{x-\cos (\theta )}{\sqrt{1+x^2-2 x \cos (\theta )}} + \sin (2 \theta )
\]Solving for $x$, (sparing you the algebra again!) we obtain $x = \cos (3 \theta ) \sec (2 \theta )$. Putting everything together, the $(x,y,z)$ that minimize the total distance traveled by Amare is
\[
x = \cos (3 \theta ) \sec (2 \theta ),\quad
y = \cos(3\theta)\sec(\theta),\quad
z = \cos(3\theta)
\]Substituting into either $h(x)$, $g(x,y)$, or $f(x,y,z)$, we obtain the minimum distance traveled by Amare (after simplification):

$\displaystyle
\text{Minimum distance } = \sin(3\theta)
$

If you read the first solution, then it should come as no surprise that the total distance is also equal to $\sqrt{1-z^2}$, since (based on the last figure of the first solution), we have $z=|AF|=|AF’|$ and $|BF’|^2 + |AF’|^2 = 1$ by the Pythagorean theorem.

Evil twin

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$.