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:
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
Assuming that the direction is random–or for any other reasonable measure of the random cuts–the relative risk diverges (becomes infinite) at midpoints of the segments that bisect the pentagon in half by area. To see this, note that as the cut direction continuously changes, the infinitesimal movement is rotation around the midpoint so as to preserve equal area, and hence the density diverges there. These points form a curved pentagonal star, which is shown in blue in the picture in your post.
As we move from the center to an edge of the pentagon, the risk profile changes as follows: High initially, rises to infinity (like inverse square root) as we approach the star, falls abruptly and then rises to infinity as we approach the star again, then falls abruptly (to a fraction of the value at the center (except at the corners)) and continues to fall further as we move away from the center.
It hadn’t occurred to me that the star could also be obtained by simply drawing the locus of midpoints of XY. Nice observation! I might edit my post to reflect this fact.
I don’t follow your argument that “relative risk diverges” at the midpoints of the segments that bisect the pentagon in half by area. How are you measuring risk?
In my solution, I’m admittedly using a simple notion of risk, which I explain is just the number of valid cuts passing through a given point. The advantage of this measure is that it is unambiguous and doesn’t depend on the random distribution of cuts. Of course, there are other ways of measuring risk.
The most natural model is that risk density at a point p is lim(ε→0, Risk(ε,p)) where Risk(ε,p) is the probability that point p is within distance ε/2 of the laser beam. Equivalent formulations include:
* Risk per width ε of the laser beam as ε→0.
* Assuming that the laser sweeps 360°, the risk density is sum(1/v_i)/(2π) where each time the beam touches the point p, v_i is the speed at which the beam moves through p. (Hence, zero speed leads to infinite risk density.)
* Using measure theory: The risk to a region is integral (over the probability distribution of the rays) of the length of the part of the ray that is in the region.
For the probability distribution of the rays, I assume that each direction is equally likely (rotational symmetry), though for divergence at the pentagonal star it is sufficient that every angle has a nonzero probability density.
Correction: lim(ε→0, Risk(ε,p)) should have been lim(ε→0, Risk(ε,p)/ε)
Very nice! I chose to calculate the star’s area instead of the inner polygon, but it looks like we agree in the case of the triangle, as we should: the ratio is .01986?
yup, that’s what I found! Area for the triangle is $\frac14(\log(8)-2)\approx 0.01986$
Hi Laurent – very cool stuff. I think if e.g. you express one of the hyperbolas in polar coordinates from the origin (0,0) as r^2 = a^2*b^2 / (b^2*cos^2(theta)-a^2*sin^2(theta)) with theta measured from the y-axis you can integrate the area under the hyperbola and get 1/2n of the total area of the polygon in a compact form. The answer will look something like 2*n *[a*b/2 * tanh-1[a/b * Xp/Yp] – Xp*Yc/2] , where (Xp, Yp) is the closest vertex of the polygon to the y-axis in the first quadrant and Yc is the Y coordinate of the center of the hyperbola and the polygon (not the origin). The first term is the total area under the hyperbola swept from the origin and the second term nets out the un-needed triangle in the swept area using Heron’s formula. Using this result and expressing result as area ratio of the large polygon I get {n,area ratios} of {3, 1.986e-2};{5, 3.339e-4};{7, 3.741e-5};{9, 7.763e-6};[11, 2.256e-6};{13, 8.133e-7};{15, 3.410e-7}. These look pretty close to your values! Thanks for the great blog!
I ran my code again and I got precisely the same numerical answers as yours, so it looks like we both probably did it right! Polar coordinates do seem like a more natural choice. Maybe I’ll take another look at my derivation and try to clean it up… thanks!
I think the numbered diagram (above “Calculating the area”) is not quite correct. The centroid (only) should be labeled 5; the other points in the inner pentagon are 3, except for the points on the line segments from the centroid to the outer pentagon’s vertices, which are 4; similarly the regions labeled “3” should be 2, except for along the line segment from the centroid to outer pentagon’s vertices, where the label is indeed 3.
I don’t think that’s true. If you imagine the centroid and draw the five bisectors, and then place a new point close to the centroid (still inside the inner pentagon), then each of the five bisectors can be perturbed slightly in order to intersect the new point.
I made a little applet that draws the bisectors so you can see what I’m talking about. I added it to the solution.
can you explain the way to get the amount of lines that divide the polygons in half?
There are infinitely many lines that divide the polygon in half. This is why the question is somewhat ambiguous and can be interpreted in many ways.