integration – 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.

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]

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

Perfect pursuit

This week’s Riddler Classic is about catching

Hames Jarrison has just intercepted a pass at one end zone of a football field, and begins running — at a constant speed of 15 miles per hour — to the other end zone, 100 yards away.

At the moment he catches the ball, you are on the very same goal line, but on the other end of the field, 50 yards away from Jarrison. Caught up in the moment, you decide you will always run directly toward Jarrison’s current position, rather than plan ahead to meet him downfield along a more strategic course.

Assuming you run at a constant speed (i.e., don’t worry about any transient acceleration), how fast must you be in order to catch Jarrison before he scores a touchdown?

Here is the solution.
[Show Solution]

For a detailed derivation (warning: calculus!) click below.
[Show Solution]

Note: This is the solution I came up with… Admittedly, it’s a bit tedious and not particularly intuitive. If you have a more direct or more elegant solution approach, I would love to hear about it!

Based on the diagram above, Jarrison starts at $(0,w)$ and runs toward $(L,w)$ at a speed $v_0$. Therefore, Jarrison’s position as a function of time is $(v_0t, w)$. We start at $(0,0)$ and we run at a speed $v$. Let’s also suppose our position at time $t$ is $(x(t),y(t))$.

We run in such a way that our velocity always points toward Jarrison. Therefore, we have:
\[
\frac{\dot y}{\dot x} = \frac{w-y}{v_0t-x},
\]where the dots denote time derivatives, i.e. $\dot x = \frac{\mathrm{d}}{\mathrm{d}t}x(t)$. To keep notation simple, we’ll omit the $(t)$ when writing $x$ or $y$. We also know that our speed is constant at $v$, therefore, we have:
\[
\dot x^2 + \dot y^2 = v^2
\]These two coupled differential equations, together with the initial conditions $x(0)=y(0)=0$, completely describe our motion. Our task is to solve these equations, and then find the value of $v$ such that the solution passes through the point $(L,w)$, i.e., we catch Jarrison right as he scores a touchdown.

To solve this problem, we’ll use the change of variables $u = \frac{\dot x}{\dot y}$. Substitute this into both equations. For the first equation, also isolate $t$ and differentiate so that $t$ no longer appears explicitly. Ultimately, we obtain:
\[
\dot u = \frac{v_0}{w-y}
\quad\text{and}\quad
\dot y = \frac{v}{\sqrt{u^2+1}}
\quad\text{with: }\begin{cases}y(0)=0 \\ u(0)=0\end{cases}
\]Combining these equations, we obtain the single ODE (in differential form)
\[
\frac{\mathrm{d}y}{w-y} = \frac{v}{v_0} \cdot \frac{\mathrm{d}u}{\sqrt{u^2+1}}
\]Integrating from $t=0$ ($y=u=0$) to an arbitrary later point, we obtain:
\[
\log\left( \frac{w}{w-y} \right) = \frac{v}{v_0} \log \left| \sqrt{u^2+1}+u \right|
\]Therefore,
\[
\frac{w}{w-y} = \left| \sqrt{u^2+1}+u \right|^{v/v_0}
\]Now note that if $\sqrt{u^2+1}+u = f$, we have $u = \frac{1}{2}\left( f-f^{-1} \right)$. Therefore, we can solve the above equation and obtain:
\[
u = \frac{1}{2}\left[ \left(1-\frac{y}{w}\right)^{-v_0/v}-\left(1-\frac{y}{w}\right)^{v_0/v} \right]
\]Now recall the definition $u = \frac{\dot x}{\dot y} = \frac{\mathrm{d}x}{\mathrm{d}y}$. Therefore,
\[
\mathrm{d}x = \frac{1}{2}\left[ \left(1-\frac{y}{w}\right)^{-v_0/v}-\left(1-\frac{y}{w}\right)^{v_0/v} \right]\mathrm{d}y
\]Integrating from $t=0$ ($y=u=0$) to an arbitrary later point, we obtain:
\[
\frac{x}{w} = \frac{1}{2}\left[ \frac{\left(1-\frac{y}{w}\right)^{1+v_0/v}-1}{1+\frac{v_0}{v}}-\frac{\left(1-\frac{y}{w}\right)^{1-v_0/v}-1}{1-\frac{v_0}{v}}\right]
\]This tells us $x$ as a function of $y$. The only thing we’re missing is $v$. To find $v$, we use the fact that the curve must pass through $(L,w)$, which leads to
\[
\frac{L}{w} = \frac{v_0 v}{v^2-v_0^2}.
\]Solving for $v$ yields:
\[
\frac{v}{v_0} = \frac{1+\sqrt{4\frac{L^2}{w^2}+1}}{2\frac{L}{w}}.
\]Note that the right-hand side is always greater than $1$, regardless of the value of $L$ or $w$. This makes sense; we need to be going faster than Jarrison if we ever hope to catch him.

When did the snow start?

This week’s Riddler Classic is a neat calculus problem:

One morning, it starts snowing. The snow falls at a constant rate, and it continues the rest of the day.

At noon, a snowplow begins to clear the road. The more snow there is on the ground, the slower the plow moves. In fact, the plow’s speed is inversely proportional to the depth of the snow — if you were to double the amount of snow on the ground, the plow would move half as fast.

In its first hour on the road, the plow travels 2 miles. In the second hour, the plow travels only 1 mile.

When did it start snowing?

Here is my solution:
[Show Solution]

Cutting polygons in half

This Riddler puzzle is about cutting polygons in half. Here is the problem:

The archvillain Laser Larry threatens to imminently zap Riddler Headquarters (which, seen from above, is shaped like a regular pentagon with no courtyard or other funny business). He plans to do it with a high-powered, vertical planar ray that will slice the building exactly in half by area, as seen from above. The building is quickly evacuated, but not before in-house mathematicians move the most sensitive riddling equipment out of the places in the building that have an extra high risk of getting zapped.

Where are those places, and how much riskier are they than the safest spots? (It’s fine to describe those places qualitatively.)

Extra credit: Get quantitative! Seen from above, how many high-risk points are there? If there are infinitely many, what is their total area?

Here is my solution:
[Show Solution]

A note on interpretations

Because the problem doesn’t explain how to define “risk”, there are two main ways to interpret the problem.

We can assume the laser cut will happen randomly, and the “risk” of a point is related to the likelihood that the cut will hit it. If the point is a geometrical point and the cut is infinitely thin, then all points have zero probability. If assume the point has a finite size, then the problem can make sense, but we still need to worry about how the cuts are distributed. For example:
- we could start by choosing the angle of the cut uniformly at random and then pick the valid cut at this angle.
- we could randomly choose a point on the perimeter and then pick the valid cut that passes through that point.
- we could pick a point uniformly at random on the inside of the area and then choose a valid cut through that point.
Each method will yield a different answer! This notion is related to Bertrand’s Paradox.
Another way to interpret the problem is to avoid probability altogether and to count the number of different admissible cuts that can pass through a point and use this as a measure of how “unsafe” the point is.

I chose interpretation #2 because it’s a well-defined problem that doesn’t require making additional assumptions. I’ll also present the solution to every polygon, because why not!

Even number of sides

Let’s start with an easy case. If the building is a square, or hexagon, or any other polygon with an even number of sides, then it’s clear by symmetry that all cuts will pass through the center of the polygon. See below for an illustration.

We can all agree that the middle of the building is very unsafe, because all cuts go through it. Meanwhile, each other point in the building has precisely one possible cut passing through it. The same holds true if we have infinitely many sides (a circular building).

Odd number of sides

If the building is a polygon with an odd number of sides instead, such as a triangle or pentagon, then things get more interesting. It turns out that not all cuts through the center divide the area into equal halves. To understand why, take a look at the pentagon below with center at $P$ and short radius $|PA’| = 1$. Extend the top and bottom edges to meet at $O$ as shown. A similar figure can be drawn for any number of sides $n$. In any case, we’ll have $\theta = \tfrac{\pi}{n}$.

Clearly $AA’$ and $BB’$ are valid cuts because by symmetry they split the area of the pentagon in half. Suppose we’d like to make $XY$ a valid cut as well. Then it follows that the area $(OAA’)$ must equal the area $(OYX)$. Define the lengths $x = |OX|$ and $y = |OY|$. Then we must have:

\[
xy = |OA’||OA| = \cot(\tfrac{\theta}{2})\left( \cot(\tfrac{\theta}{2}) + \tan(\theta) \right) = \cot^2(\tfrac{\theta}{2})\sec(\theta)
\]

If $P$ is the origin, the Cartesian coordinates of $X$ and $Y$ are

\[
X = \begin{bmatrix}x \,-\, \cot(\tfrac{\theta}{2}) \\ -1 \end{bmatrix}
\qquad
Y = \begin{bmatrix}y\cos(\theta) \,-\, \cot(\tfrac{\theta}{2}) \\ y\sin(\theta) \,-\, 1 \end{bmatrix}
\]

As $X$ slides from $A’$ to $B’$, $Y$ will slide from $A$ to $B$ in such a way that the product $xy$ remains constant. What we’d like to know is the shape of the curve that the line $XY$ traces out as it assumes all allowable configurations. One way to do this is to compute a parametric equation for the line $XY$. To do this, compute the vector $X + t(Y – X)$. Then, eliminate $y$ to obtain the following family of points:

\[
Z(x,t) = \begin{bmatrix}
(1-t)x + \frac{t}{x} \cot^2(\tfrac{\theta}{2}) \,-\, \cot(\tfrac{\theta}{2}) \\ -1 + \frac{t}{x}\cot^2(\tfrac{\theta}{2})\tan(\theta) \end{bmatrix}
\]

Where $t \in [0,1]$ and $x \in [\cot(\tfrac{\theta}{2}) ,\cot(\tfrac{\theta}{2}) +\tan(\theta)]$. We don’t care about all of these points, however. We only want the boundary of the curve. To find it, fix one coordinate and maximize the other. e.g. let $\eta = -1 + \frac{t}{x}\cot^2(\tfrac{\theta}{2})\tan(\theta)$, solve for $x$ in terms of $\eta$ and $t$, substitute this into the first component of $Z(x,t)$, to obtain an expression that only depends on $\eta$ and $t$. This will be a quadratic in $t$ that is maximized when $t=\tfrac{1}{2}$. Therefore, the equation of the locus of points is simply $Z(x,\tfrac{1}{2})$. If the polygon has $n$ sides, there will be $n$ such loci, each rotated about $P$ by an angle $\frac{2k\pi}{n}$, for $k=0,1,\dots,n-1$. In the figure below, I plotted the result for the case $n=3,5,7$ (click to enlarge).

Here are the diagrams repeated, but this time with some cuts drawn in and zoomed in to the middle portion (click to enlarge).

The blue lines are the boundaries to the regions of interest. Inside each region, all the points have the same number of valid cuts through them. For example, in the triangle case:

the points inside the blue shape belong to three distinct cuts.
the points on the boundary of the blue shape belong to two distinct cuts.
the points outside the blue shape each belong to precisely one cut.

In the figure below, I labeled the case $n=5$ with the number of cuts for each portion.

Calculating the area

The bonus question asks about the number of “high-risk” points. In our interpretation, this would be the points in the innermost blue pentagon (it’s not quite a pentagon since its sides are slightly curved). The points in the middle each have five intersecting cuts. In general, in the case of an $n$-sided polygon ($n$ must be odd, of course), the high-risk area will also be (roughly) an $n$-sided polygon located in the middle.

We can calculate the area of this shape, but I wasn’t able to find an elegant way to do it. Roughly, my approach was as follows:

Start with parametric equations $x(t)$ and $y(t)$ for each of the curves.
Solve for the intersection points between adjacent rotated versions of the curves (these are the vertices of the inner rounded polygon).
Convert these intersection points into an interval $t \in [t_1,t_2]$ that allows our original parametric equations to sweep out one side of the inner rounded polygon.
Integrate to find the area of the radial sector of the inner polygon using the cross-product formula for area:
\[
A = \int_{t_1}^{t_2} |x'(t) y(t) – x(t) y'(t)|\,dt
\]
Multiply the area of the sector by $n$ to get the total area of the inner rounded polygon.
Divide by the total area of the polygon ($n \tan(\theta)$) in our case to get the area ratio.

The details aren’t particularly interesting. Thank goodness for Mathematica… The final result for the area ratio is:
laser_eqn

Doesn’t appear to be a way to simplify this. For what it’s worth, this function goes to zero very fast, to the tune of $\tfrac{1}{256}\theta^6$. Here is what it looks like graphically.

The area ratio for the case $n=5$ turns out to be $0.000333883\dots$, or about $\frac{1}{3000}$.

Pretty pictures

Congratulations for making it this far! Here is a neat visualization of the regions. I gave each cut thickness and transparency and used evenly spaced angles. The first picture has about 50 thick cuts while the second picture has about 2000 thin cuts. Click the figure to enlarge.

And here is a bonus interactive graphic showing the solution

A clever integral

I was recently reminded of this problem from one of my favorite books: Problem-Solving Through Problems. The problem originally appeared in the 1980 Putnam Competition.

Evaluate the following definite integral.

\[
\int_0^{\pi/2} \frac{\mathrm{d}x}{1 + (\tan x)^{\sqrt{2}}}
\]

The solution:
[Show Solution]