calculus - Book Proofs

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

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.

Infinite cake

This week’s Riddler Express is a short problem about infinite series. Let’s dig in! (I paraphrased the question)

You and your infinitely many friends are sharing a cake, and you come up with several different methods of splitting it.

Friend 1 takes half of the cake, Friend 2 takes a third of what remains, Friend 3 takes a quarter of what remains after Friend 2, Friend 4 takes a fifth of what remains after Friend 3, and so on.
Friend 1 takes $1/2^2$ (or one-quarter) of the cake, Friend 2 takes $1/3^2$ (or one-ninth) of what remains, Friend 3 takes $1/4^2$ of what remains after Friend 3, and so on.
Same as previous, with even denominators only: Friend 1 takes $1/2^2$ of the cake, Friend 2 takes $1/4^2$ of what remains, Friend 3 takes $1/6^2$ of what remains after Friend 2, and so on.

For each of these methods, after your infinitely many friends take their respective pieces, how much cake is left?

Here is my solution
[Show Solution]

For each different method, let’s call $x_n$ the amount of cake remaining after the first $n$ friends have taken their share. Since we start with a full cake, $x_0=1$. The amount of cake remaining after all friends have taken their share is therefore $\lim_{n\to\infty} x_n$.

Method 1

In this method, Friend number $n$ takes $\frac{1}{n+1}$ of what remains, which is $\frac{1}{n+1}x_{n-1}$. After this happens, the amount of cake remaining is:
\[
x_n = x_{n-1}-\frac{1}{n+1}x_{n-1} = \left(1-\frac{1}{n+1}\right)x_{n-1}.
\]The net result is therefore:
\begin{align}
x_n &= \left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{4}\right)\cdots\left(1-\frac{1}{n+1}\right) \\
&= \left(\frac{1}{2}\right)\left(\frac{2}{3}\right)\left(\frac{3}{4}\right)\cdots\left(\frac{n}{n+1}\right) \\
&= \left(\frac{1}{\bcancel{2}}\right)\left(\frac{\bcancel{2}}{\bcancel{3}}\right)\left(\frac{\bcancel{3}}{\bcancel{4}}\right)\cdots\left(\frac{\bcancel{n}}{n+1}\right) \\
&= \frac{1}{n+1}
\end{align}This is an example of a telescoping series; all the terms in the middle cancel out and we are left with $\frac{1}{n+1}$ of the cake after all friends have gone. Unfortunately, this tends to zero as $n\to\infty$, so with this method, there will be no cake left after all friends have gone!

Method 2

In this method, Friend number $n$ takes $\frac{1}{(n+1)^2}$ of what remains. Using an approach similar to the previous method, we are left with:
\begin{align}
x_n &= \left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{3^2}\right)\left(1-\frac{1}{4^2}\right)\cdots\left(1-\frac{1}{(n+1)^2}\right) \\
&= \left(\frac{2^2-1}{2^2}\right)\left(\frac{3^2-1}{3^2}\right)\left(\frac{4^2-1}{4^2}\right)\cdots \left(\frac{(n+1)^2-1}{(n+1)^2}\right) \\
&= \left(\frac{1\cdot 3}{2 \cdot 2}\right)\left(\frac{2\cdot 4}{3 \cdot 3}\right)\left(\frac{3\cdot 5}{4\cdot 4}\right)\cdots \left(\frac{n\cdot(n+2)}{(n+1)(n+1)}\right) \\
&= \left(\frac{1\cdot \bcancel{3}}{2 \cdot \bcancel{2}}\right)\left(\frac{\bcancel{2}\cdot \bcancel{4}}{\bcancel{3} \cdot \bcancel{3}}\right)\left(\frac{\bcancel{3}\cdot \bcancel{5}}{\bcancel{4}\cdot \bcancel{4}}\right)\cdots \Biggl(\frac{\bcancel{n}\cdot(n+2)}{\bcancel{(n+1)}(n+1)}\Biggr) \\
&= \frac{n+2}{2(n+1)}.
\end{align}In the third step, we used the difference of squares formula $n^2-1 = (n-1)(n+1)$ to again obtain a telescoping series. This time, however, the sum is $\frac{n+2}{2(n+1)}$, for which the limit $n\to\infty$ is $\frac{1}{2}$. So half of the cake is left after all friends have gone.

Method 3

In this method, Friend number $n$ takes $\frac{1}{(2n)^2}$ of what remains. Again using an approach similar to the previous methods, we obtain.
\begin{align}
x_n &= \left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{4^2}\right)\left(1-\frac{1}{6^2}\right)\cdots\left(1-\frac{1}{(2n)^2}\right).
\end{align}While it looks deceptively similar to the two previous examples solved above, this infinite product is substantially more complicated since there is no telescoping. There is a way to approach this using calculus, but I will instead show a proof using complex analysis that I think is a bit more intuitive.

Every polynomial $p(z)$ of degree $n$ can be factored as $p(z)=a(z-c_1)\cdots(z-c_n)$ where the $c_k$ are zeros of the polynomial (they may be complex numbers). This result can be extended to the case where $p(z)$ is an infinite polynomial with infinitely many zeros. This is known as the Weierstrass factorization theorem. Roughly speaking, if $f(z)$ is an entire function (it must have a power series expansion that is valid everywhere), then we can write it as an infinite product $f(z)=a(z-c_1)(z-c_2)\cdots$ where the $c_k$ are zeros of the infinite polynomial.

Consider the function $f(z) = \frac{\sin(\pi z)}{\pi z}$. This is an entire function because $\sin(\pi z)$ has a power series that is valid everywhere and it has no constant term (recall $\sin(x) = x-\frac{1}{3!}x^3+\frac{1}{5!}x^5-\cdots$) so we can divide through by $\pi z$ and we get another valid power series. The places where $f(z)=0$ correspond to $z \in \{\pm1,\pm2,\pm3,\dots\}$. Note also that $f(0) = \lim_{z\to 0} \frac{\sin(\pi z)}{\pi z} = 1$. By the Weierstrass factorization theorem (I’m skipping some technical details here), we can write:
\begin{align}
f(z) &= a(1-z)(1+z)\left(1-\frac{z}{2}\right)\left(1+\frac{z}{2}\right)\left(1-\frac{z}{3}\right)\left(1+\frac{z}{3}\right)\cdots \\
&= a\left(1-z^2\right)\left(1-\frac{z^2}{2^2}\right)\left(1-\frac{z^2}{3^2}\right)\cdots
\end{align}Since $f(0) = 1$, it must be the case that $a=1$. So we have the series:
\[
\frac{\sin(\pi z)}{\pi z} = \left(1-z^2\right)\left(1-\frac{z^2}{2^2}\right)\left(1-\frac{z^2}{3^2}\right)\cdots.
\]This is known as the Euler infinite product representation for the sinc function. Substituting $z=\frac{1}{2}$, the infinite product becomes exactly the one we wanted to evaluate for how much cake is left:
\[
\left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{4^2}\right)\left(1-\frac{1}{6^2}\right)\cdots = \frac{2}{\pi} \approx 0.6366.
\]This infinite product (or its inverse, rather) also has a name; it’s called the Wallis product.

Bonus: Odd-numbered terms

As a side note, if we only keep the odd-numbered terms of the product, we obtain:
\[
\left(1-\frac{1}{3^2}\right)\left(1-\frac{1}{5^2}\right)\left(1-\frac{1}{7^2}\right)\cdots = \frac{\pi}{4} \approx 0.7854.
\]This can be proved using a similar approach, this time with the function:
\[
\cos\left(\frac{\pi z}{2}\right) = (1-z^2)\left(1-\frac{z^2}{3^2}\right)\left(1-\frac{z^2}{5^2}\right)\left(1-\frac{z^2}{7^2}\right)\cdots
\]It then follows that:
\[
\left(1-\frac{1}{3^2}\right)\left(1-\frac{1}{5^2}\right)\left(1-\frac{1}{7^2}\right)\cdots
= \lim_{z\to 1} \frac{\cos\left(\frac{\pi z}{2}\right)}{1-z^2} = \frac{\pi}{4}
\]As a sanity check, we found that using the even terms gives $\frac{2}{\pi}$ and using the odd terms gives $\frac{\pi}{4}$. So using all the terms gives $\frac{2}{\pi}\cdot \frac{\pi}{4} = \frac{1}{2}$, which is what we found using “Method 2”!

Baking the biggest pie

This week’s Riddler Classic is about baking the biggest pie. Just in time for π day!

You have a sheet of crust laid out in front of you. After baking, your pie crust will be a cylinder of uniform thickness (or rather, thinness) with delicious filling inside.

To maximize the volume of your pie, what fraction of your crust should you use to make the circular base (i.e., the bottom) of the pie?

Here is my solution:
[Show Solution]

Since we have a fixed amount of crust that we will shape into a cylinder, the problem is one of maximizing the volume for a fixed area. This is known as the isovolume problem (which is a misnomer; it should really be called the isoarea problem).

Let’s suppose the crust has an area of $A$. Given this area, we would like to maximize the volume of the cylinder. Let’s suppose the radius of the base is $r$ and the height is $h$. Then the formulas are:
\[
A = 2\pi r^2 + 2\pi r h \qquad\text{and}\qquad V = \pi r^2 h.
\]Since the area $A$ is fixed, we are not free to choose $r$ and $h$ independently. Once $r$ is chosen, $h$ is uniquely determined by the equation for $A$. Solving for $h$ in terms of $A$ from the area equation, we obtain:
\[
h = \frac{A-2\pi r^2}{2\pi r}
\]Substituting this value of $h$ into the equation for $V$, we obtain:
\[
V= \frac{1}{2} r (A-2\pi r^2)
\]Here is a plot of what this function $V(r)$ looks like for a value of $A=1$:

We can maximize $V$ by looking for an $r$ such that $\frac{\mathrm{d}V}{\mathrm{d}r}=0$ and $\frac{\mathrm{d}^2V}{\mathrm{d}r^2}\lt 0$. In other words, at the optimal choice of $r$, the tangent to the curve $V(r)$ is flat and the curvature is negative (curves downward). This leads to the equations:
\[
\frac{1}{2}(A-6\pi r ^2) = 0 \qquad\text{and}\qquad -6\pi r \lt 0
\]Since $r\geq 0$ (radius can’t be negative), the second equation is always satisfied, and the first equation implies that $r=\sqrt{\frac{A}{6\pi}}$. If $A=1$ as in the plot above, this leads to $r=0.23033$, which looks about right! With the optimal choice of $r$, the corresponding choice of $h$ becomes $h=\sqrt{\frac{2A}{3\pi}}$ and the corresponding optimal volume is $V=\frac{A^{3/2}}{3\sqrt{6\pi}}$. Interestingly, we can observe that with these choices,
\[
2r = 2\sqrt{\frac{A}{6\pi}} = \sqrt{\frac{4A}{6\pi}} = \sqrt{\frac{2A}{3\pi}} = h
\]So in order to maximize the area, the diameter should be equal to the height! In other words, when viewed from the side, our pie should have a square shape; we’ll be making more of a cake rather than a pie.

The fraction of crust used for the base of the optimal pie is:
\[
\frac{\pi r^2}{A} = \frac{\pi \left(\frac{A}{6\pi}\right)}{A} = \frac{1}{6}.
\]

$\displaystyle
\begin{aligned}
&\text{So we should use $\tfrac{1}{6}$ of the crust for the base, $\tfrac{1}{6}$ for the top,}\\
&\text{and the remaining $\tfrac{2}{3}$ for the sides.}
\end{aligned}$

One way to explain the shape of this tall pie is to think back to the isovolume problem discussed earlier. The solution to the isovolume problem is a sphere. So in order to be as efficient as possible, the pie’s shape should be as close to a sphere as possible, hence the tall shape. For a sphere, $A=4\pi r^2$ and $V=\frac{4}{3}\pi r^3$, so by eliminating $r$, we obtain $V=\frac{A^{3/2}}{6\sqrt{\pi}}$.

If we take the ratio of the volume of the sphere and the volume of the optimized cylinder, we obtain:
\[
\frac{V_\text{cylinder}}{V_\text{sphere}} = \frac{ \frac{A^{3/2}}{3\sqrt{6\pi}} }{ \frac{A^{3/2}}{6\sqrt{\pi}} } = \sqrt{\frac{2}{3}} \approx 0.8165
\]So the optimized cylindrical pie will have a volume which is about 82% of the largest possible volume.

Bonus: Different bottom and top area

If the top and bottom areas of the pie have different radii, then the shape is no longer a cylinder, but rather a frustom of a cone. The formulas are now a bit more complicated, because they depend on two radii ($r$ and $R$) and the height $h$:
\begin{align}
A &= \pi (r+R) \sqrt{h^2+(R-r)^2}+\pi \left(r^2+R^2\right)\\
V &= \frac{1}{3} \pi h \left(r^2+r R+R^2\right)
\end{align}Using a similar procedure as before (solving for $h$ in the area equation and substituting this into the volume equation), we obtain the following volume formula that depends only on the radii of the top and bottom
\[
V = \frac{\left(r^2+r R+R^2\right) \sqrt{\left(A-2 \pi r^2\right) \left(A-2 \pi R^2\right)}}{3 (r+R)}
\]A necessary condition for optimality is that both partial derivatives are zero, namely $\frac{\partial V}{\partial r} = \frac{\partial V}{\partial R} = 0$. This leads to the equations:
\begin{align}
\frac{\partial V}{\partial r} &= -\frac{r \left(A-2 \pi R^2\right) \left(2 \pi \left(4 r^2 R+2 r^3+2 r R^2+R^3\right)-A (r+2 R)\right)}{3 (r+R)^2 \sqrt{\left(A-2 \pi r^2\right) \left(A-2 \pi R^2\right)}} \\
\frac{\partial V}{\partial R} &= -\frac{R \left(A-2 \pi r^2\right) \left(2 \pi \left(2 r^2 R+r^3+4 r R^2+2 R^3\right)-A (2 r+R)\right)}{3 (r+R)^2 \sqrt{\left(A-2 \pi r^2\right) \left(A-2 \pi R^2\right)}}
\end{align}Much messier than the ordinary cylinder case… But we can simplify this. It must be true that $A\gt 2\pi R^2$ and $A\gt 2\pi r ^2$, since the area of the smaller circle plus the area of the sides must be at least the area of the larger circle (they are only equal when the pie is flat). So if $\frac{\partial V}{\partial r} = \frac{\partial V}{\partial R} = 0$, we can cancel a bunch of terms and we are left with:
\begin{align}
2 \pi \left(4 r^2 R+2 r^3+2 r R^2+R^3\right)-A (r+2 R) &= 0& &(1) \\
2 \pi \left(2 r^2 R+r^3+4 r R^2+2 R^3\right)-A (2 r+R) &= 0& &(2)
\end{align}This still looks rather messy to solve, but we can make a clever observation. If we subtract one equation from the other $(2)-(1)$ and factor, we obtain:
\[
(R-r) \left(A+2 \pi r^2+6 \pi r R+2 \pi R^2\right)=0
\]The right factor consists of a sum of positive terms, and therefore must be positive. So we conclude that $R=r$. Put another way, the only way we’ll have an optimized volume is if the top and bottom circles are of equal size. This reduces our more complicated case to the simpler case we already solved above.

Flip to freedom

This week’s Riddler Classic is a problem about coin flipping. The text of the original problem is quite long, so I will paraphrase it here:

There are $n$ prisoners, each with access to a random number generator (generates uniform random numbers in $[0,1]$) and a fair coin. Each prisoner is given the opportunity to flip their coin once if they so choose. If all of the flipped coins come up Heads, all prisoners are released. But if any of the flipped coins come up Tails, or if no coins are flipped at all, the prisoners are not released. If the prisoners cannot communicate in any way and do not know who is flipping their coin or not, how can they maximize their chances of being released?

Here is my solution:
[Show Solution]

This problem is a balancing act. If $k$ of the prisoners flip their coins, the chance of being released is
\[
\mathrm{Prob}(\text{win if }k\text{ coins are flipped})=\begin{cases} 0 & k=0\\ \frac{1}{2^k} & k=1,2,\dots,n\end{cases}
\]The best-case scenario is if $k=1$ prisoner flips their coin and the others do not, ensuring the maximum probability of release of $1/2$. But how should the prisoners decide who flips their coin? If they were allowed to communicate ahead of time, they could elect somebody to flip their coin. But since the prisoners cannot communicate so there is no way to plan ahead!

Since each prisoner has access to a random number generator, they can use it to decide whether they should be flipping their coin or not. Here is the strategy. We must decide on a threshold $t$. Each prisoner queries their random number generator and if the number they obtain is less than $t$, they flip their coin. The larger $t$ is, the more likely prisoners are to flip coins. So there is a trade-off between ensuring at least one prisoner flips a coin and ensuring not too many prisoners flip coins. Let’s figure out the best choice of $t$.

Let’s call the probability the prisoners are released $f_n(t)$. It depends on the threshold they choose. Now,
\begin{align*}
f_n(t) &= \sum_{k=1}^n \frac{1}{2^k} \mathrm{Prob}(\text{there are }k\text{ flips}) \\
&= \sum_{k=1}^n \frac{1}{2^k} \binom{n}{k}t^k(1-t)^{n-k} \\
&= \sum_{k=1}^n \binom{n}{k}\left(\frac{t}{2}\right)^k (1-t)^{n-k} \\
&= ( 1-\tfrac{1}{2}t)^n-(1-t)^n
\end{align*} In the last step, we used the Binomial Theorem to evaluate the sum. So our goal is to find $t\in[0,1]$ that minimizes $f_n(t)$. Here is what the function looks like for different values of $n$:

As anticipated, there is an ideal value of the threshold $t$ that maximizes the probability of winning. However, the maximum depends on $n$, the number of prisoners. To find the maximum, we can use calculus: set the derivative of $f_n(t)$ equal to zero:
\[
\frac{\mathrm{d}f_n(t)}{\mathrm{d}t}=n(1-t)^{n-1}-\tfrac{1}{2}n(1-\tfrac{1}{2}t)^{n-1}=0
\]Solving for the optimal threshold $t$, we obtain:

$\displaystyle
t_\text{opt}=1-\frac{1}{2^{n/(n-1)}-1}
$

As a function of $n$, $t_\text{opt}$ is the threshold each prisoner should use. If their random number generator produces a value less than the threshold, they should flip their coin. Otherwise, they should not. As anticipated, in the limit $n\to\infty$, $t_\text{opt}\to 0$ because as the number of prisoners increases, we want each prisoner to be less likely to flip their coin. As an approximation, the first order asymptotic expansion of $t_\text{opt}$ is
\[
t_\text{opt} = \frac{2\log(2)}{n} + O\left(\frac{1}{n^2}\right)\approx\frac{1.386}{n}
\]So this can be used as a quick way to approximate the threshold (in case the prisoners don’t have access to a calculator!).

How about the probability of winning assuming the prisoners use this strategy? This simply amounts to evaluating $f_n(t_\text{opt})$. Doing so, we obtain:

$\displaystyle
\textrm{Prob}(\text{win}) = \frac{1}{\left(2^{n/(n-1)}-1\right)^{n-1}}
$

Here is a table comparing the optimal threshold and corresponding probability of winning for different values of $n$:

Number of prisoners	threshold $t_\text{opt}$	Probability of freedom
1	1	0.5
2	0.666667	0.333333
3	0.453082	0.299119
4	0.342037	0.284842
5	0.274529	0.277001
10	0.13802	0.262709
50	0.0277034	0.252429
100	0.0138574	0.251208

So when $n=1$, the lone prisoner flips every time and the probability of winning is $\frac{1}{2}$. With two prisoners, each prisoner should flip $\frac{2}{3}$ of the time, and the probability of winning is $\frac{1}{3}$. As $n\to\infty$, the threshold goes to zero as described above, and we can also verify that the probability of winning tends to $\frac{1}{4}$ in the limit.

So this strategy ensures that the probability of all prisoners being released is always at least 25%. The only caveat is that in order to compute which threshold to use, the prisoners must know $n$, the total number of prisoners playing the game.

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]

Settlers in a circle

In this Riddler problem, the goal is to spread out settlements in a circle so that they are as far apart as possible:

Antisocial settlers are building houses on a prairie that’s a perfect circle with a radius of 1 mile. Each settler wants to live as far apart from his or her nearest neighbor as possible. To accomplish that, the settlers will overcome their antisocial behavior and work together so that the average distance between each settler and his or her nearest neighbor is as large as possible.

At first, there were slated to be seven settlers. Arranging that was easy enough: One will build his house in the center of the circle, while the other six will form a regular hexagon along its circumference. Every settler will be exactly 1 mile from his nearest neighbor, so the average distance is 1 mile.

However, at the last minute, one settler cancels his move to the prairie altogether (he’s really antisocial). That leaves six settlers. Does that mean the settlers can live further away from each other than they would have if there were seven settlers? Where will the six settlers ultimately build their houses, and what’s the maximum average distance between nearest neighbors?

Here is my solution:
[Show Solution]

I approached this problem from a modeling and optimization perspective. If there are $N$ settlers and we imagine the coordinates of the settlers are $(x_i,y_i)$ for $i=1,\dots,N$ and $d_i$ is the distance between the $i^\text{th}$ settler and its nearest neighbor, then we can model the problem as follows:
\[
\begin{aligned}\underset{x,y,d\,\in\,\mathbb{R}^N}{\text{maximize}} \quad & \frac{1}{N}\sum_{i=1}^N d_i \\
\text{such that} \quad & x_i^2 + y_i^2 \le 1 &&\text{for }i=1,\dots,N\\
& (x_i-x_j)^2 + (y_i-y_j)^2 \ge d_i^2 &&\text{for }i,j=1,\dots,N\text{ and }j\ne i
\end{aligned}
\]The objective is to minimize the average distance between each settler and its nearest neighbor (the average of the $d_i$). The first constraint says that each settler must be within the circle (a distance of at most $1$ from the origin). The second constraint says that the $i^\text{th}$ settler is a distance at least $d_i$ from each of the other settlers.

The game is then to find $(x_i,y_i,d_i)$ that satisfy these constraints and maximize the objective. Broadly speaking, this is an example of a mathematical optimization problem. Unfortunately, the problem as stated is nonconvex problem because of the form of the second constraint. This means that the problem may have local maximizers that are not globally optimal. There are two ways forward:

First, we could use local search: start with randomly placed settlers, wiggle their positions in ways such that the objective continues to increase, and then stop once we can no longer improve the objective. Examples of such approaches include hill-climbing and interior-point methods. In general, such approaches only find local maxima, so we should try many random starting positions to ensure we find the best possible answer.

Second, we could use global search: these are methods that attempt to find a globally optimal solution by considering many configurations simultaneously and adding random perturbations that can “kick” a solution out of a local maximum. Examples include simulated annealing and particle swarms. These approaches tend to be much slower than local search, but they have a much better chance of finding a global optimum.

Ultimately, I used local search with several random initializations. Here is how the maximum average distance scales with the number of settlements.

The bar plot also shows how well we would do if we distributed the settlements evenly on the circumference (“all on the border”) and if we put one in the middle and the rest evenly distributed on the circumference (“one in the center”). We can also examine what the settlement distributions actually look like. Here they are:

The case $N=6$ is particularly interesting because it has a settlement that is almost in the center, but not quite. Indeed, the average minimum distance to neighbors for this case is $1.002292$, so we benefit ever so slightly by placing one settlement off-center.

We can solve for the $N=6$ case analytically as well, but the solution isn’t pretty (fair warning!) It turns out the settlements are distributed throughout the circle in the following way:

Here, $x$ is the distance between the origin and the point $A$. The other distances satisfy $z \lt y \lt x+1$, and the average distance to the nearest neighbor is therefore $\tfrac{1}{6}(1+x+2y+3z)$. Note that once we set $x$, this uniquely determines the positions of all the other points. After some messy trigonometry, we obtain the following equations relating $x$, $y$, $z$ and two auxiliary variables $p$ and $q$:
\begin{align}
y^2&=1+x-x^2-x^3\\
z^2&=1-x^2+2x\left(pq-\sqrt{1-p^2}\sqrt{1-q^2}\right) \\
p&= \tfrac{1}{2}(1-2x-x^2)\\
q&= \tfrac{1}{2}(1-x+x^2+x^3)
\end{align}We can eliminate $\{y,z,p,q\}$ and solve for the average distance $\bar d = \frac{1+x+2y+3z}{6}$ as a function of $x$ alone:
\[
\bar d = \frac{x+1}{12} \left(2+4 \sqrt{1-x}+3 \sqrt{2}\sqrt{1-x} \sqrt{\left(x^3+2 x^2-x+2\right)-x \sqrt{x+3} \sqrt{x^3+x^2-x+3}} \right)
\]We can then plot this function of $x$, and we get the following curve:

Interestingly, this function reaches its maximum just a bit after $x=0$. Zooming in, we can see more clearly:

The maximum occurs at about $x=0.0555108$ and the maximum value is $1.00229$, just as we found before. If we try to solve for this analytically by taking the derivative of this function, setting it equal to zero, and eliminating rationals, we obtain the following result… That the optimal $x$ a root of the following $30^\text{th}$ order polynomial:
\begin{align}
x^{30}&+\tfrac{152}{9} x^{29}+\tfrac{9259}{81} x^{28}+\tfrac{6851}{18} x^{27}+\tfrac{383363 }{648}x^{26}+\tfrac{1999495} {5832}x^{25}\\
&+\tfrac{43478263}{52488} x^{24}+\tfrac{75726373}{23328} x^{23}+\tfrac{3282369305}{1679616} x^{22}-\tfrac{31642768891}{7558272} x^{21}\\
&+\tfrac{367775655235}{136048896} x^{20}+\tfrac{392027905801}{34012224} x^{19}-\tfrac{2016793647847}{136048896} x^{18}-\tfrac{1258157703385}{68024448} x^{17}\\
&+\tfrac{4545130566235}{136048896} x^{16}-\tfrac{22059424877}{17006112} x^{15}-\tfrac{8448216227365}{136048896} x^{14}+\tfrac{2878062707167}{68024448} x^{13}\\
&+\tfrac{7398046956073}{136048896} x^{12}-\tfrac{312655708903}{3779136} x^{11}+\tfrac{17266856539}{1679616} x^{10}+\tfrac{63670102441}{839808} x^9\\
&-\tfrac{29827845749}{559872} x^8-\tfrac{541401565}{23328} x^7+\tfrac{619158287}{23328} x^6+\tfrac{6168305}{2592} x^5\\
&-\tfrac{156285}{32} x^4-\tfrac{5153}{36} x^3+\tfrac{3923}{12} x^2+\tfrac{45}{2} x-\tfrac{35}{16}
\end{align}Yuck! Here is what you get if you plot this polynomial; as expected, there is a root at $x=0.0555108$.

Alice and Bob fall in love

In this interesting Riddler problem, we’re dealing with a possibly unbounded sequence of… children? Here it goes:

As you may know, having one child, let alone many, is a lot of work. But Alice and Bob realized children require less of their parents’ time as they grow older. They figured out that the work involved in having a child equals one divided by the age of the child in years. (Yes, that means the work is infinite for a child right after they are born. That may be true.)

Anyhow, since having a new child is a lot of work, Alice and Bob don’t want to have another child until the total work required by all their other children is 1 or less. Suppose they have their first child at time T=0. When T=1, their only child is turns 1, so the work involved is 1, and so they have their second child. After roughly another 1.61 years, their children are roughly 1.61 and 2.61, the work required has dropped back down to 1, and so they have their third child. And so on.

(Feel free to ignore twins, deaths, the real-world inability to decide exactly when you have a child, and so on.)

Five questions: Does it make sense for Alice and Bob to have an infinite number of children? Does the time between kids increase as they have more and more kids? What can we say about when they have their Nth child — can we predict it with a formula? Does the size of their brood over time show asymptotic behavior? If so, what are its bounds?

Here is an explanation of my derivation:
[Show Solution]

Let’s call $t_k$ the time at which Alice and Bob have their $k^\text{th}$ child. The first child is born at time zero, so $t_1 = 0$. Since the work due to a child is one divided by their age, the work due to child $k$ at time $t$ is given by:
\[
\text{work at time }t = \begin{cases}
\frac{1}{t-t_k} & \text{if }t > t_k \\
0 & \text{otherwise}
\end{cases}
\]We also know that each new child is born once the total work due to all previous children equals $1$. Therefore, we have the following equations:
\begin{align}
t_2\text{ satsifies:} && \frac{1}{t_2-t_1} &= 1 \\
t_3\text{ satisfies:} && \frac{1}{t_3-t_2} + \frac{1}{t_3-t_1} &= 1 \\
t_4\text{ satisfies:} && \frac{1}{t_4-t_3} + \frac{1}{t_4-t_2} + \frac{1}{t_4-t_1} &= 1 \\
\cdots\qquad \\
t_k\text{ satisfies:} && \sum_{i=1}^{k-1} \frac{1}{t_k-t_i} &= 1
\end{align}and so on. We also know that $t_1 \lt t_2 \lt t_3 \lt \ldots$ since the children are born sequentially. The nice thing about these equation is that they can be solved sequentially. We know that $t_1=0$. Substituting this into the first equation yields $t_2=1$. Substituting these values into the second equation yields:
\[
\frac{1}{t_3-1}+\frac{1}{t_3} = 1
\]Rearranging yields $t_3^2-3t_3+1=0$. This equation has two solutions, but we take the one that satisfies $t_3 \gt t_2$, and we obtain $t_3=\tfrac{3+\sqrt{5}}{2} \approx 2.618$. We can continue in this fashion, solving each subsequent equation by substituting the previous values… but things get complicated in a hurry. The next equation becomes:
\[
t_4^3-\left(\tfrac{11+\sqrt{5}}{2}\right)t_4^2+\left(\tfrac{13+3\sqrt{5}}{2}\right)t_4-\left(\tfrac{3+\sqrt{5}}{2}\right)=0
\]Once again, we find that there is a unique solution that satisfies $t_4 \gt t_3$. This solution is approximately $t_4\approx 4.5993$. There doesn’t appear to be any automatic way to continue this process. Every time we try to compute the next $t_k$, we have to find the root of an even more complicated polynomial!

We’ll take a numerical approach, but let me first address one issue: how can we be sure that these ever-more-complicated polynomials always have a root that satisfies our constraints? For example, what if the polynomial for $t_4$ had no roots larger than $t_3$? What if it had many such roots? Thankfully, there is a simple way we can guarantee that there is always exactly one admissible root to each polynomial by leveraging the intermediate value theorem. Specifically, the function
\[
f_k(t) = \frac{1}{t-t_1} + \frac{1}{t-t_2} + \cdots + \frac{1}{t-t_{k-1}}
\]with $t \gt t_{k-1} \gt \ldots \gt t_1$ is a continuous and strictly decreasing function. Moreover, $\lim_{t\to {t_{k-1}}^+}f_k(t) = +\infty$ and $\lim_{t\to\infty} f_k(t) = 0$. Therefore, by the intermediate value theorem, there must be some point $t_k \in (t_{k-1},\infty)$ such that $f_k(t_k)=1$. The strict monoticity of $f_k$ ($f_k$ is strictly decreasing) implies that this $t_k$ must be unique.

The root may be unique, but how can we find it efficiently? Here, we can leverage a further property of $f_k$; namely convexity. The fact that $f_k$ is convex (and smooth) means that we can leverage some efficient methods from convex analysis that make use of derivative information. There are many ways to get the answer from here… What I ended up doing was to use the L-BFGS algorithm on the objective $(f_k(t)-1)^2$. My implementation in Julia using the Optim.jl package took about 40 seconds to evaluate birth dates of the first 1,000 children.

Note: there are many ways to formulate this as an optimization problem. One way is to note that solving $f_k(t)=1$ is equivalent to extremizing the antiderivative of $f_k(t)-1$. In other words, we could solve:
\[
t_k = \underset{t \gt t_{k-1}}{\text{arg min}} \left( t-\sum_{i=1}^{k-1}\log(t-t_i) \right)
= \underset{t \gt t_{k-1}}{\text{arg max}}\,\, e^{-t}\prod_{i=1}^{k-1}(t-t_i)
\]Incidentally, this last expression for $t_k$ makes it clear that there should be a unique $t_k$. When $t\gt t_{k-1}$, the product is a polynomial that is strictly increasing, and it’s multiplied by $e^{-t}$, which will drive it to zero eventually. There must therefore be a unique maximizer. I tried implementing both of these approaches and both turned out to be slower than directly minimizing $(f_k(t)-1)^2$.

If you’re just interested in the answers to the questions, here they are:
[Show Solution]

Does it make sense for Alice and Bob to have an infinite number of children? Biological limitations aside, yes! We proved that for each $t_k$, there exists a unique $t_{k+1} \gt t_k$ that satisfies the constraints of the problem. So by induction, Alice and Bob can have as many children as they like.
Does the time between kids increase as they have more and more kids? The answer is yes, and I will provide a “proof by picture”. After finding $t_k$ for $k=1,2,\dots$, we know the birth dates of each child. Then it remains to compute $(t_{k+1}-t_k)$ for each $k$ (the time between births). Here is the plot

The first point on the left says that we wait $1$ year after child $1$ is born, we wait about $1.6$ years after child $2$ is born, and so on. Plotted on a log scale as above, we see the curve is almost a perfect straight line. Here is a formula we can use to approximate the number of years to wait:

$\displaystyle
\text{years to wait after child }k\text{ is born} \,\approx\, 1 + 2.19\cdot \log_{10} k
$

So yes, the time between children increases (without bound), but it does so slowly. By the time Alice and Bob have their 1,000th child, they will be waiting approximately 7.5 years between kids.
What can we say about when they have their $N^\text{th}$ child? Is there a formula we can write down? I couldn’t find an analytic expression, but I did find a pretty good approximation. First, let’s make a plot to see what we’re working with. Here is what the birth years is like for the first 19 children

We can see here that the growth rate is slightly faster than linear. Since the time between children fit so well to a curve of the form $a+b\log x$, it makes sense to fit the birth dates themselves to the integral of this form. In an effort to fit the simplest possible curve, I did a bit of experimenting and found that the form $a x + x \log x$ does a really good job. I found the equation of best fit using linear regression and put the equation in the plot above. If we extend the time horizon, we get a similar result:

This is a pretty good fit; the plot actually depicts the true data with the fit overlaid on top. The fit is so good that you can’t even see the data underneath! So for large $N$, a good approximation is:

$\displaystyle
\text{year when child }N\text{ is born} \,\approx\,-0.315N + N\log N
$
The final question is whether the size of the brood over time shows asymptotic behavior. We already plotted the time of birth vs child number, and found the relationship to be approximately: $y \approx -0.315 N + N\log N$. So here, we need to look at the inverse relationship and ask what $N$ does as a function of $y$. Since $y$ grows a little faster than linearly, this means $N$ will grow a little more slowly than linearly.

Tether your goat!

A geometry problem from the Riddler blog. Here it goes:

A farmer owns a circular field with radius R. If he ties up his goat to the fence that runs along the edge of the field, how long does the goat’s tether need to be so that the goat can graze on exactly half of the field, by area?

Here is my solution:
[Show Solution]

There are many ways to solve this problem, so I figured I would pick an unorthodox way: using calculus! Consider the diagram below.

The circular field is centered at $O$. The goat is tethered at $C$ and the tether has length $r$. Let $B$ be the point diametrically opposed to $C$ and let $A$ be the farthest point along the perimeter that the goat can reach. Let $\theta$ be the angle $BOA$, as shown. If $r$ changes a little bit, by some amount $dr$, then $\theta$ will change by some amount $d\theta$. Likewise, the fraction of the total area reachable by the goat will change by $dA$. Let’s calculate how these quantities are related.

First, note that $dA$ is simply the area between the two circular arcs centered at $C$ and passing through $A$ and $A’$, respectively. We must also divide by the total area of the field in order to get a ratio. As $dr\to 0$, we have:
\[
dA = \frac{\tfrac{1}{2} \theta\, d(r^2)}{\pi R^2}
\]Our next task is to find out how $d\theta$ is related to $d(r^2)$. Look at the triangle $OAC$. By the law of cosines, we have:
$r^2 = 2R^2(1 + \cos(\theta))$. Taking differentials, we obtain:
\[
d(r^2) = -2R^2 \sin(\theta)\,d\theta
\]Substituting back into our expression for $dA$, we obtain:
\[
dA = -\tfrac{1}{\pi} \theta\,\sin(\theta)\,d\theta
\]We can now integrate! Note that $A=1$ when $\theta=0$. Therefore, we have:
\begin{align}
A(\theta) &= 1 + \int_{0}^\theta \tfrac{1}{\pi} t\, \sin(t)\,dt \\
&= \frac{\pi + \theta\,\cos(\theta)-\sin(\theta)}{\pi}
\end{align}This tells us the ratio of areas as a function of $\theta$. If we want this as a function of $r$ instead, we can use the law of cosines again to eliminate $\theta$ and write $A$ as a function of $r$. This yields:
\[
A(\rho) = 1+\frac{\left(\frac{\rho ^2}{2}-1\right) \cos ^{-1}\left(\frac{\rho ^2}{2}-1\right)}{\pi }-\frac{\rho \sqrt{4-\rho ^2}}{2\pi}
\]where I made the substitution $\rho := r/R$. We can plot this quantity as a function of $\rho$, and we get:

As we might expect, when $r=0$, $A=0$. And the area ratio grows monotonically with $r$ until we reach $r=2R$, at which point the goat can reach the farthest point (which is point $B$) and therefore can reach the entire field. There is no closed-form expression for the exact tether length that leads to a particular area ratio, since that would require solving the above $A(\rho)$ for $\rho$. However, we can easily solve the equation numerically. Doing so, we obtain:

$\displaystyle
\frac{\text{length of tether}}{\text{radius of field}} \approx 1.15873
$

Finally, here is a diagram of what the field and tether look like when the area ratio is exactly 1/2.