geometry - Book Proofs

Stop the alien invasion!

Today’s puzzle is from The Riddler, and has to do with spherical geometry.

A guardian constantly patrols a spherical planet, protecting it from alien invaders that threaten its very existence. One fateful day, the sirens blare: A pair of hostile aliens have landed at two random locations on the surface of the planet. Each has one piece of a weapon that, if combined with the other piece, will destroy the planet instantly. The two aliens race to meet each other at their midpoint on the surface to assemble the weapon. The guardian, who begins at another random location on the surface, detects the landing positions of both intruders. If she reaches them before they meet, she can stop the attack.

The aliens move at the same speed as one another. What is the probability that the guardian saves the planet if her linear speed is 20 times that of the aliens’?

Here is my solution for the case of interest, where the guardian is faster than the intruders.
[Show Solution]

Fast guardian, flat planet

The fact that everything takes place on a sphere makes matters complicated, so let’s start with a simpler problem: suppose the world is flat, and we would like to know the set of possible starting points for the guardian such that the planet is saved. Let the alien starting locations be $A$ and $B$, and denote their rendezvous point $M$ (the midpoint of $AB$). Let $X$ be the point along $AB$ where the guardian intercepts one of the intruders. If the guardian is $q$ times faster than the intruders, then by the time an intruder has traveled to $X$, the guardian may have traveled a distance $q$ times greater. Therefore, the set of locations the guardian could have come from is a circle centered at $X$ and of radius $r = \min(AX,BX)$. See below for an illustration.

intercept1

Since the guardian is faster than the intruders ($q \ge 1$), then the guardian might as well intercept at $M$. In other words, the possible guardian starting points for $M$ contains the starting points for all other intercept locations! The following animation shows the case $q=1.5$. The red circle shows the set of starting points for the guardian that leads to saving the planet (it’s a circle of radius $\tfrac{1}{2} q \cdot AB$ centered at $M$).

a15

Fast guardian, spherical planet

Things get interesting when the planet is spherical. Here, the solution is the same in principle, but wrapped around a sphere. Again, let $A$ and $B$ be the intruders’ positions. The shortest path connecting $A$ and $B$ is a great circle of angle $0 \le \theta \le \pi$. If $q \ge 1$, the guardian’s positions that guarantee safety will be a spherical cap defined by an angle $\tfrac{1}{2}q \theta$.

If $\tfrac{1}{2}q \theta \ge \pi$, then the guardian will always be able to intercept the intruders, leading to certain safety. If the angle is less than $\pi$, the ratio of unsafe area to total area is

\[
\frac{\text{unsafe area}}{\text{total area}} = \frac{2\pi R^2 \left(1 – \cos(\pi – \tfrac{1}{2}q \theta)\right)}{4\pi R^2} = \frac{1}{2}\left(1 + \cos(\tfrac{1}{2}q \theta)\right)
\]

Therefore, the probability that the planet is destroyed as a function of $\theta$ is:

\[
f(\theta) = \begin{cases}
\frac{1}{2}\left(1 + \cos(\tfrac{1}{2}q \theta)\right) & \theta \le \frac{2\pi}{q} \\
0 & \theta > \frac{2\pi}{q}
\end{cases}
\]

Note that if $1 \le q < 2$, then $\frac{2\pi}{q} > \pi$ and so the second case never occurs; planetary destruction is always a possibility if the guardian is less than twice as fast as the intruders! In order to calculate the total probability, we need to average over all $\theta$, since the distribution of the intruders’ starting locations is random. However, it’s not as simple as averaging over $\theta$, as doing so would bias the distribution towards small $\theta$. Since we want the distribution to be uniform over the sphere, the angle $\theta$ will have probability distribution $p(\theta) = \tfrac{1}{2}\sin\theta$. For more information about where this comes from see this article. The total probability of destruction is therefore

\begin{align}
\int_0^\pi f(\theta) p(\theta) \, d\theta
&= \int_0^{\min(\pi,\,2\pi/q)} \frac{1}{2}\left(1 + \cos\bigl(\tfrac{1}{2}q \theta\bigr)\right) \frac{1}{2}\sin\theta\, d\theta \\
&= \begin{cases}
\frac{6-q^2+2 \cos\bigl(\tfrac{\pi q}{2}\bigr)}{2 (4-q^2)} & 1 \le q < 2 \\ \frac{q^2-8-q^2 \cos\bigl(\tfrac{2 \pi }{q}\bigr)}{4 (q^2-4)} & q \ge 2 \end{cases} \end{align} To find the probability of safety, we compute $1$ minus the probability of destruction, and we obtain:

$\displaystyle
\mathbb{P}(\text{planet is saved}) = \begin{cases}
\frac{2-q^2-2 \cos\bigl(\tfrac{\pi q}{2}\bigr)-6}{2 (4-q^2)} & 1 \le q < 2 \\ \frac{3q^2-8-q^2 \cos\bigl(\tfrac{2 \pi }{q}\bigr)}{4 (q^2-4)} & q \ge 2 \end{cases} $

Here is a plot of the probability of safety as a function of the guardian’s relative speed.

To answer the specific question asked, if the guardian’s speed is $20$ times the speed of the intruders, the probability that the planet will be saved is

$\displaystyle
\mathbb{P}(\text{planet is saved}) =\frac{149+50\cos(\pi/10)}{198} \approx 99.27\%
$

So with a guardian this fast, there is a very good chance the planet will be safe from the aliens!

Here is a partial solution for the more complicated case where the guardian is slower than the intruders.
[Show Solution]

If the guardian is slower than the intruders ($0 < q < 1$), then the solution is no longer a circle, because it might happen that the guardian cannot intercept at $M$ but can intercept at some other point along $AB$. The following animation illustrates the case $q=0.5$. The red shape shows the set of starting points for the guardian that leads to saving the planet (it’s a circle of radius $\tfrac{1}{2} q \cdot AB$ centered at $M$ together with the region enclosed by the tangent segments drawn to $A$ and $B$).

a05

Unfortunately, things get very ugly from here. If we map the situation onto a sphere, then the segments on either side are no longer straight lines, of course, but they aren’t great circles either! To find the boundary of interest, let’s say the intruder that starts at $B$ is intercepted at $T$, and the guardian leaves from $D$. If we assume the guardian just barely makes it to $T$, then the arc $\widehat{DT}$ should be $q$ times the arc $\widehat{BT}$. Let’s suppose $\phi$ is fixed, and we’ll seek the maximum possible $\psi$ such that there exists some $\tau$ such that $D$ reaches $T$ in time.

After some ugly math, we can solve for the set of $(\phi,\psi)$ as follows: fix $\phi$, then solve for $\tau$ such that $\tan(\tau-\phi) = q \tan(q\tau)$. If the associated $\tau$ is greater than $\tfrac{1}{2}\theta$, then simply set $\tau = \tfrac{1}{2}\theta$. Then, find $\psi$ such that $\cos(\tau-\phi)\cos\psi = \cos (q\tau)$.

So for each fixed $\phi$, we can use the above procedure to find $\tau$ and $\psi$. By symmetry, we can repeat on the other side to get the part of the curve where we intercept the intruder leaving $A$ instead. Unfortunately, these equations do not admit an analytic solution, so they must be solved numerically. We can visualize what the region will look like, but there doesn’t appear to be a nice way to solve for its boundary or compute its area. Nevertheless, here is an illustration of the “safe zone” where the guardian will be able to intercept the intruders, for the case $q=0.5$.

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

The puzzle of the picky eater

Today’s Riddler post is a neat problem about calculating areas.

Every morning, before heading to work, you make a sandwich for lunch using perfectly square bread. But you hate the crust. You hate the crust so much that you’ll only eat the portion of the sandwich that is closer to its center than to its edges so that you don’t run the risk of accidentally biting down on that charred, stiff perimeter. How much of the sandwich will you eat?

Extra credit: What if the bread were another shape — triangular, hexagonal, octagonal, etc.? What’s the most efficient bread shape for a crust-hater like you?

Here is my solution:
[Show Solution]

As with the problem of the overflowing martini glass, it’s possible to solve the present problem without using any calculus, relying on properties of conic sections. The first thing to know is that the set of points equidistant from a point (called the focus) and a line (called the directrix) is a parabola. In fact, this is the definition of a parabola!

The center of the sandwich is the focus and each crusty edge a directrix. Together, they define parabolas that separates the “safe-to-eat” from the “unsafe-to-eat” parts of the sandwich. If the sandwich is a regular polygon with $n$ sides, the edible region will be the union of $n$ parabolic segments. Due to the symmetry in the problem, it suffices to examine half of one of the segments.

bread_parabola bread_parabola2 But how do we compute areas? We’ll use the following property of parabolas: the tangent line at any point makes equal angles to the lines that meet up with the focus and the directrix. The website cut-the-knot has a very elegant and visual proof of this fact. So in the figure to the right, $\angle FPT = \angle P’PT$. Consequently, for incremental areas (blue and yellow), both have the same base and height and so the blue area is half the yellow area. Summing up all these incremental areas, we can see that the area swept by the parabola will be exactly half of the area between the parabola and the directrix. We illustrate this fact in the next figure. Note that $\theta=\frac{\pi}{n}$ (e.g. $\theta=45^\circ$ for square bread).

We can calculate $x$ by computing the length of $FG$ in two different ways. Namely: $FG = 1-x = x\cos\theta$
Therefore, $x = (1+\cos\theta)^{-1}$. What we’re really after is the fraction of the total area that is blue, which we’ll call $E$. Let’s first compute the fraction that is pink by using similar triangles. This gives us:
\[
\frac{B}{B+A+A/2} = x^2
\]

We can now compute the fraction that is blue by simple algebra:
\[
E =
\frac{A/2}{B+A+A/2} = \frac{1}{3}\left(1 – \frac{B}{B+A+A/2}\right) = \frac{1-x^2}{3}
\]

Substituting the $x$ we found before into the expression for $E$, we get our final answer:

$\displaystyle
E(n) = \frac{1}{3} \left( 1 \,-\, \frac{1}{(1+\cos\tfrac{\pi}{n})^2} \right)
$

For $n=4$ (square bread), we obtain $E(4)=\frac{1}{3}(4\sqrt{2}-5) \approx 0.219$. As we increase $n$, $E(n)$ increases as well, as shown in the plot below.

$bread_fraction$

In the limit as $n\to\infty$, $\cos\frac{\pi}{n} \to 1$, and we obtain $E(\infty) = \frac{1}{4}$, which makes sense because the polygon becomes a circle and then the portion that is eaten is just a circle with half the radius (one quarter of the area). The circle is therefore the most efficient shape. It would be interesting to investigate non-polygonal shapes as well, but then we’d have to come up with a non-ambiguous way of defining the “center” of the shape.

Here is a figure showing the part of the sandwich that gets eaten as we change the number of sides.

I made the above figure using the following Mathematica script:

Table[ n = 4i + j + 3;  θ = π/n;  L = 1/Cos[θ]; 
Rx = Apply[And, Table[ x^2 + y^2 ≤ (1 + Sin[2θ k]x + Cos[2θ k]y)^2, {k,0,n-1} ]];
Ax = Apply[And, Table[ Sin[2θ k]x - Cos[2θ k]y ≤ 1, {k,0,n-1} ]];
RegionPlot[{Rx,Ax}, {x,-L,L}, {y,-L,L}, PlotPoints->40, Frame->None],
{i,0,1}, {j,0,3} ] //MatrixForm

Overflowing martini glass

This Riddler puzzle is all about conic sections.

You’ve kicked your feet up and have drunk enough of your martini that, when the conical glass (🍸) is upright, the drink reaches some fraction p of the way up its side. When tipped down on one side, just to the point of overflowing, how far does the drink reach up the opposite side?

Here is my solution:
[Show Solution]

Suppose the martini glass has a sidelength $L$ and top radius $r$ (see figure below). We’ll compare the volume of liquid in both configurations, which will give us the desired relationship between $p$ and $q$. It turns out we can use a simple proportionality argument without needing to actually compute either volume.

martini

In the configuration on the left, the liquid cone is a shape similar to that of the entire glass, but with each dimension scaled by $p/L$. Therefore the volume of the liquid is proportional to $p^3$.

Moving forward, we’ll need to know a bit about conic sections. Namely, the intersection of a plane with a cone is always either an ellipse, a hyperbola, or a parabola. You can learn more about conic sections here.

Now consider the configuration on the right. The volume of the liquid cone is $\frac13 \times (\text{area of liquid surface})\times (\text{height})$. The liquid surface is a conic section (an ellipse), which has area $\pi s w$, where $s$ and $w$ are the major and minor radii respectively. Rewrite the volume as: $\frac{\pi}{3} \times w \times (s \times \text{height} )$.

The product $(s \times \text{height})$ is simply the lateral area of the liquid when viewed from the side. This triangle has one side $L$, one side $q$, and the angle between them (the tip of the glass) is fixed. Therefore this lateral liquid area is proportional to $ q$.

The minor radius $w$ belongs to a plane that passes through the midpoint of the liquid surface as well as the midpoint of the top opening of the glass (with radius $r$). By similar triangles, this slice is parallel to the opposite edge of the glass so the conic section is a parabola this time. It follows that $w$ is proportional to $\sqrt{q}$.

Putting everything together, the volume of the liquid on the right is proportional to $q \times \sqrt{q} = q^{3/2}$. The volumes of liquid in both configurations are equal so we conclude that $p^3 \propto q^{3/2}$. Or, in other words, $q \propto p^2$. To find the constant of proportionality, observe that when $p=L$, we also have $q=L$. Therefore:

\[
\left(\frac{q}{L}\right) = \left(\frac{p}{L}\right)^2
\]

So when you tip the glass to the point of overflowing, the drink reaches up the opposite side of the glass a fraction equal to the square of the fraction reached when the glass is level.