Book Proofs - A blog for mathematical riddles, puzzles, and elegant proofs

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

How to beat Roger Federer at Wimbledon

This Riddler problem is about the game of tennis!

Your wish has been granted, and you get to play tennis against Roger Federer in his prime in the Wimbledon final. You have only a 1 percent chance to win each point, but Roger, sporting gentleman that he is, offers to let you name any score and begin the match at that point. (So, if you’ve entertained a fantasy of storming back after being down three match points in the fifth set, now’s the time to live it.) What score can you name that gives you the best chance to win, and what is your chance of winning the title?

A rough (and approximate) solution:
[Show Solution]

Here is the rundown of how tennis is scored:

A match is won by the first player to win three sets. Therefore up to five sets will be played. The first four sets are ordinary sets while the fifth set (if necessary) is an advantage set.
An ordinary set is won by the first player to (i) win six ordinary games and (ii) have a two game lead. If the score ever gets to 6-6, then a special tiebreak game is played, and the winner of that game wins the set.
An advantage set is like an ordinary set, but with no tiebreak. There is no limit on the number of games needed.
An ordinary game is won by the first player to (i) win four points and (ii) have a two point lead. No limit on the number of points needed.
A tiebreak game is won by the first player to (i) win seven points and (ii) have a two point lead. No limit on the number of points needed.

It may seem at first glance that the most advantageous score is to be up 2 sets to 0, to be winning the third set 5 games to 0, and to be winning the sixth game of that set 40-love (3 points to 0). If we’re going to beat Roger, it will most likely happen during that 40-love game. If Roger gets past this, he’ll almost certainly win the rest of the match. There are many ways Roger could win the 40-love game. He could win 5 point in a row (probability $(0.99)^5 \approx 0.951$). Or he could win three in a row, lose one of the next two games, then win two in a row (probability $2(0.01)(0.99)^6 \approx 0.019$), and so on. All other possibilities are increasingly unlikely so let’s stop here and call it roughly $0.970$. So we have roughly a 3% chance of beating Roger if we start with this score.

This is not the best starting score, however! As mentioned above, tiebreak games are played to seven points instead of four! So the most advantageous score is actually to be up 2 sets to 0, to have the third set tied 6 games to 6, and to be winning the tiebreak game 6-0. Then, using an argument similar to the one above, we can approximate Roger’s chances of winning as $(0.99)^8( 1 + 2(0.01)(0.99) ) \approx 0.941$.

We have roughly a 5.9% chance of beating Roger.

A more detailed (and exact) solution:
[Show Solution]

The fair case

We’ll start by calculating what happens in the fair case (where Federer doesn’t give you a head start). Let’s step aside from tennis for a second and imagine a generic game where a sequence of rounds is played. Each round, a point is awarded either to me with probability $q$, or to my opponent otherwise. We will play until one of us gets $m$ points and wins by two. In the event that we tie at $m-1$ points each, then we flip a weighted coin to break the tie. In such a coin flip, I win with probability $r$. Let $f_m(q,r)$ be the probability that I win this game.

The probability that I win with a score of $m$ to $k$ is given by ${m+k-1 \choose k} q^m (1-q)^k$, since I must win the final game and my opponent will win $k$ of the remaining $m+k-1$ games. The tie occurs with probability ${2m-2 \choose m-1} q^{m-1}(1-q)^{m-1}$ and in this case I win with probability $r$. So we have:

\[
f_m(q,r) = \sum_{k=0}^{m-2} {m+k-1 \choose k} q^m (1-q)^k + {2m-2 \choose m-1} q^{m-1}(1-q)^{m-1}r
\]

The first case of interest is when the game is tied (deuce), and we will play until one player wins by two. Let’s call $x_d,x_f,x_m$ the probability of winning given that the current score is “deuce”, “advantage Federer”, or “advantage me”, respectively. Also, suppose that the probability that I win one point is $p$. Then we can write the following sets of equations:

\begin{align}
x_d &= p x_m + (1-p) x_f \\
x_f &= p x_d \\
x_m &= p + (1-p) x_d
\end{align}

Therefore, the probability that I win a game if the score is deuce is:

\[
x_d(p) = \frac{p^2}{1-2p+2p^2}
\]

We can now build up the entire match one piece at a time.

Each ordinary game is won at 4 points, win by 2, and if we tie at 3-3 then we are at deuce. So my probability of winning a game is:
\[
g = f_4(p,x_d(p))
\]
Each tiebreak game is won at 7 points, win by 2, and if we tie at 6-6 then we are at deuce. So my probability of winning a tiebreak game is:
\[
\bar g = f_7(p,x_d(p))
\]
Each ordinary set is won at 6 games, win by 2, and if we tie at 5-5, we play two more games. I can win by winning both extra games or by winning one of the two games and then winning a tiebreak game. So if we tie at 5-5, my chance of winning is $g^2 + 2g(1-g)\bar g$. So my overall chance of winning an ordinary set is:
\[
s = f_6(g, g^2 + 2g(1-g)\bar g)
\]
Each advantage set is won at 6 games, win by 2, and if we tie 6-6 then we are at deuce. So my probability of winning an advantage set is:
\[
\bar s = f_6( g, x_d(g) )
\]
The match is won at 3 sets, win by 2, and if we tie at 2-2 then we play an advantage set. So my probability of winning a match is:
\[
M = f_3( s, \bar s)
\]

While it’s possible to actually calculate these quantities, the result is pretty messy. For those interested, $M(p)$ is a rational function whose numerator has degree 465 and denominator has degree 136. Yuck! So I won’t write it out… but here is what the functions look like as plots:

I didn’t include advantage sets on the plot because they have virtually the same distribution as ordinary sets. As expected, the picture is perfectly symmetric; if we have a 50% chance of winning every point, then we have a 50% chance of winning every game, every set, and the entire match. The shape also makes sense; if we are worse than our opponent, then winning a game or a set or a match becomes progressively less likely.

Here are some exact numbers for those who are interested:

P(win point) P(win game) P(win set) P(win match)

49% 47.5% 42.9% 36.8%

45% 37.7% 18.5% 4.61%

40% 26.4% 3.65% 0.04%

1% 1.50×10^-7 2.35×10^-39 1.30×10^-115

So if your chance of winning one point is 1%, your chance of beating Federer is roughly the same as your odds of winning the Mega-Million jackpot 14 times in a row. Not good.

The unfair case

As discussed before, we’ll want to start with a 2-0 set lead in the match. The third set will be tied 6-6 and we’ll be up 6-0 in the tiebreak game.
To find our chance of winning in this case, we will instead calculate our chance of losing, because the algebra is simpler. We need to calculate:

\begin{align}
&\mathbb{P}(\text{lose match})\\
&= \mathbb{P}(\text{lose tiebreak up 6-0}) \times \mathbb{P}(\text{lose match up 2-1}) \\
&= \mathbb{P}(\text{lose 6 points}) \times \mathbb{P}(\text{lose deuce}) \times \mathbb{P}(\text{lose 1 set}) \times \mathbb{P}(\text{lose 1 adv. set}) \\
&= (1-p)^6(1-x_d(p))(1-s)(1-\bar s)
\end{align}

Once again, we can evaluate this quantity algebraically, and it turns out to be a mess… it’s a rational function of $p$ whose numerator has degree 182 and whose denominator has degree 60. But there is a trick: we can approximate $s\approx \bar s \approx 0$, i.e. we just give up if we don’t win that first tiebreak, and we get a much simpler formula:

$\displaystyle
\mathbb{P}(\text{win match}) \approx 1\, -\, \frac{(1-p)^8}{1-2p+2p^2}
$

To verify that this approximation is a good one, I plotted both the true function and the approximation on the same axes:

Here is a plot showing the difference between the curves (on a log scale):

So if we have $p=0.01$ as specified in the problem, the approximation will be correct to 36 decimal digits! The final numerical result is:

$\displaystyle
\mathbb{P}(\text{win match}) = 5.86159\%
$

So our original approximation of 5.9% wasn’t far off.

What if robots cut your pizza?

This Riddler puzzle is about random chords of a circle and the regions they describe.

At RoboPizza™, pies are cut by robots. When making each cut, a robot will randomly (and independently) pick two points on a pizza’s circumference, and then cut along the chord connecting them. If you order a pizza and specify that you want the robot to make exactly three cuts, what is the expected number of pieces your pie will have?

Here is a simple solution, which was pointed out to me in a comment to my original post.
[Show Solution]

Let’s say the robot cuts $n$ random chords. Due to the way in which the chords are randomly chosen, two different chords will never begin or end at the exact same point along the circumference. Moreover, any time chords intersect inside the circle, that intersection will involve exactly two chords. We don’t need to worry about cases where three cuts perfectly intersect in a single point (i.e. the way you’d normally cut a pizza!), since that will never happen.

Instead of counting the number of pieces $S$, we can count the number of intersections instead! By Euler’s Formula, we have that

\[
(\text{# vertices } V)\, -\, (\text{# edges }E) + (\text{# faces }F) = 2
\]

We have to be a bit careful to apply this formula correctly. If we have $n$ chords and $p$ intersections, there will be $V = 2n+p$ vertices (count the ones on the circumference). Each internal intersection adds an edge, and we must count the arcs between cuts along the circumference as edges, so we have a total of $E = 3n+2p$. Finally, there will be $F = S+1$ faces, since the entire circle counts as a face in Euler’s formula. Substituting these into the formula $V-E+F=2$, we obtain: $S = n+p+1$. So instead of counting the number of pizza pieces, we’ll count the number of intersections and then add $n+1$.

To find the expected number of intersections, suppose we have $n$ chords and let $X_{ij} = 1$ if chords $i$ and $j$ intersect, and $0$ otherwise. We’ll let $C$ be the set of all pairs of chords $(i,j)$. Then the expected number of intersections is:

\begin{align}
\mathbb{E} \left[ \sum_{(i,j) \in C} X_{ij} \right]
= \sum_{(i,j) \in C} \mathbb{E}\bigl[X_{ij}\bigr]
= {n \choose 2} \mathbb{E}\bigl[X_{12}\bigr]
\end{align}

Although the $X_{ij}$ are not mutually independent, linearity of expectation holds regardless. By symmetry each $\mathbb{E}\bigl[X_{ij}\bigr]$ is the same, and is equal to the probability that two random chords intersect. We show in the next solution that this probability is $\tfrac{1}{3}$, so the expected number of pieces is $\tfrac{1}{3}{n \choose 2} + n + 1$, which is equal to:

$\displaystyle
\mathbb{E}\bigl[\text{number of pieces}\bigr] = \frac{(n+2)(n+3)}{6}
$

In the case where we have $n=3$ cuts, the expected number of pieces is $5$.

The following solution is a bit more complicated, and computes the entire distribution rather than just its expected value.
[Show Solution]

We can think of the cutting process as happening in two stages. First, we choose $2n$ points randomly along the circumference. Then, we assign labels to the points: $A_1$, $A_2$, $B_1$, $B_2$, and so on. Then, we draw chords from $A_1$ to $A_2$, $B_1$ to $B_2$, and so on. The key observation is that the placement of the points (the first step) is irrelevant. Only the label assignment is relevant to determining the number of intersections points.

For example, consider the case $n=2$. If we assign labels to points in a clockwise fashion as: $A_1, B_2, A_2, B_1$ to the four points, then there will always be one intersection point. Similarly, if we assign the labels in the order: $A_2,A_1,B_1,B_2$, there will always be zero intersections. It doesn’t matter where the four points are, the only thing that matters is the order of the labels!

Due to symmetry, the number of intersections doesn’t change if we swap $A_1$ and $A_2$, or even if we swap $A$ and $B$. So ultimately, we only need to count the number of different pairs of points that can be chosen!

Here is a diagram showing the breakdown for $n=2$. Keep in mind that the location of each point doesn’t change. We’re merely choosing how we pair the points up.

So there are $3$ possible ways to choose pairs, two of which have $3$ pieces and one of which has $1$ piece. So the expected number of pieces is

\[
S_2 = \left(\tfrac{2}{3}\times 3\right) + \left(\tfrac{1}{3} \times 4\right) = \tfrac{10}{3}
\]

The probability of the two chords intersecting is $\tfrac{1}{3}$ (we make use of this in the first solution to the problem). The $n=3$ case is a bit more complicated because there are more ways to choose pairs, but the idea is the same. Here is a diagram showing the breakdown.

The expected number of pieces is therefore:

\[
S_3 = \left(\tfrac{5}{15}\times 4\right) + \left(\tfrac{6}{15} \times 5\right) + \left(\tfrac{3}{15} \times 6\right) + \left(\tfrac{1}{15} \times 7\right) = 5
\]

The expected number of pieces is 5.

One final point of interest: the way in which the chords are randomly chosen is important! If we had used a different method, e.g. by picking a random radius and a random point on that radius, and then constructing a chord perpendicular to the radius through this chosen point, then we would obtain a different answer! The approach above works because the way the chords are chosen allows us to decouple how endpoints are chosen from how labels are assigned. To learn more about why the randomization method is important, take a look at Bertrand’s Paradox.

If you’ve already read the solution above and you’re interested in the distribution of pieces for the general case, read on!
[Show Solution]

This genre of problem involving chords of circles, intersections, regions, and so on, has quite a history. The specific problem of characterizing intersections was first posed and solved in the 1930’s, and since then, some elegant solutions have been found for the general case where there are $n$ chords. The solution I’ll summarize below is drawn mostly from the following 1975 paper:

John Riordan. “The Distribution of Crossings of Chords Joining Pairs of 2n Points on a Circle”. Mathematics of Computation, 29(129):215–222, 1975. A pdf of this paper is freely available here.

The approach described in Riordan’s paper uses generating functions. Define $T_{nk}$ to be the number of ways of choosing $n$ pairs of points among $2n$ general points such that there are $k$ intersections, and let $T_n(x)$ be the polynomial with $T_{nk}$ as coefficients:

\[
T_n(x) = \sum_{k=0}^{K} T_{nk} x^k,\qquad\text{where }K = {n \choose 2}
\]

The reason the sum goes up to $K$ is that since each pair of chords can intersect at most once, $n$ chords will produce at most $n \choose 2$ intersections. The key result from the paper above is that

\[
T_n(x) = \frac{1}{(1-x)^n} \sum_{j=0}^n (-1)^j a_{n+j,n-j}\, x^{j(j+1)/2}
\]

Here, $a_{nm}$ is a ballot number, which counts the following thing: suppose there is an election where candidate $A$ has $n$ votes and candidate $B$ has $m$ votes, with $n \ge m$. Then $a_{nm}$ is the number of ways the election results can come in (one vote at a time) such that $A$ always has at least as many votes as $B$ in the cumulative count. Another interpretation is that $a_{mn}$ is the number of “North-East” lattice paths from $(0,0)$ to $(n,m)$ that do not cross the diagonal points $(i,i)$. A closed-form expression is:

\[
a_{n+j,n-j} = \frac{2j+1}{n+j+1}{2n \choose n+j} %=\frac{2j+1}{2n+1}{2n+1 \choose n-j}
\]

In the case where $j=0$, we recover the so-called Catalan numbers, which show up in a variety of combinatorial problems.

Using the above formula for $T_n(x)$, we can expand the right-hand side as a series and compare coefficients in order to obtain $T_{nk}$. Here are the result obtained for $T_n(x)$ for $n=1,\dots,4$:

\begin{align}
T_1(x) &= 1 \\
T_2(x) &= 2 + x \\
T_3(x) &= 5 + 6 x + 3 x^2 + x^3 \\
T_4(x) &= 14 + 28 x + 28 x^2 + 20 x^3 + 10 x^4 + 4 x^5 + x^6
\end{align}

Examining the coefficients, we see that the cases $n=2$ and $n=3$ match up with what we found in the first solution. To turn these counts into probabilities, simply divide each coefficient by $T_n(1)$, which is the total number of ways of choosing pairs of points. This sum turns out to have the closed-form expression $T_n(1) = \tfrac{n!}{2^n}{2n \choose n}$. The Catalan numbers show up as the constant coefficients $C_n = T_n(0)$. In other words, $C_n$ is the number of ways of assigning chords such that there are no intersections.

The expected number of pizza pieces also has a closed-form expression, which is $S_n = \frac{1}{6}(n+2)(n+3)$. Here are some plots of the distribution of pieces for different values of $n$.

In the limit as $n\to\infty$, the distribution approaches a Gaussian with mean $S_n$ and variance $\tfrac{1}{45}n(n-1)(n+3)$. For more information on these limits and how to derive them, there is a more recent paper here:

Philippe Flajolet and Marc Noy. “Analytic Combinatorics of Chord Diagrams”. [Research Report] RR-3914, INRIA. 2000. A pdf of this paper is freely available here.

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

The blue-eyed islanders

Today’s Riddler problem is another classic. The current incarnation of the puzzle is about error-prone mathematicians, while the classic version is about blue-eyed islanders.

A university has 10 mathematicians, each one so proud that, if she learns that she made a mistake in a paper, no matter how long ago the mistake was made, she resigns the next Friday. To avoid resignations, when one of them detects a mistake in the work of another, she tells everyone else but doesn’t inform the mistake-maker. All of them have made mistakes, so each one thinks only she is perfect. One Wednesday, a super-mathematician, whom all respect and believe, comes to visit. She looks at all the papers and says: “Someone here has made a mistake.”

What happens then? Why?

Here is the solution:
[Show Solution]

On the tenth Friday, all mathematicians will resign. To understand why this happens, we’ll use a recursive approach similar to what we did for the puzzle of the pirate booty.

For simplicity, we’ll say a mathematician is flawed if they made a mistake, and perfect otherwise. Let’s look at the world through the eyes of Alice, one of the ten mathematicians. Alice doesn’t know whether she is flawed or not. She does, however, know how many of her colleagues are flawed.

According to the problem statement, all the mathematicians are flawed. So Alice sees that all nine of her colleagues are flawed. Let’s solve a simpler version of the problem first. What if none of Alice’s colleagues were flawed? In this case, the news that “someone here has made a mistake” can only mean one thing: that “someone” must be Alice! So Alice will resign on Friday.

What if exactly one of Alice’s colleagues is flawed? Two possibilities:

If Alice is perfect, then the flawed mathematician will see that everyone else is perfect and resign on Friday, just as Alice would have done in the previous case when she saw her colleagues were all perfect.
If Alice is flawed, then nothing happens on Friday. Alice then deduces that she must be flawed and resigns on the next Friday.

What if exactly two of Alice’s colleagues are flawed? Two possibilities:

If Alice is perfect, then each flawed mathematician sees one other flawed mathematician. As in the previous case, we expect them to both resign on the second Friday.
If Alice is flawed, then nothing happens on the second Friday. In that case, Alice will know of her flaw and resign on the third Friday.

The pattern is clear: if Alice has $k$ flawed colleagues but Alice is perfect, then the flawed mathematicians all resign on the $k^\text{th}$ Friday. If Alice is flawed, then nothing happens on the $k^\text{th}$ Friday, and Alice resigns on the $(k+1)^\text{st}$ Friday (along with all the other flawed mathematicians). In particular, if all ten mathematicians are flawed as in the problem statement, they all resign on the tenth Friday.

But but but…

It seems that we have a paradox — we aren’t telling the mathematicians anything they don’t already know! Each mathematician can clearly see that they have flawed colleagues, so why should explicitly announcing this fact make any difference? The answer lies in the distinction between mutual knowledge and common knowledge.

If everybody knows some proposition $P$ to be true, then $P$ is mutual knowledge. However, if everybody knows $P$, and everybody knows that everybody knows $P$, and everybody knows that everybody knows that everybody knows $P$, and so on, then $P$ is common knowledge. Although the fact that there is at least one flawed mathematician is mutual knowledge, it is not common knowledge. When the super-mathematician makes her announcement that there is at least one flawed mathematician, it becomes common knowledge, and this makes all the difference.

Rather than giving a detailed solution, I will defer to some other existing solutions online that are already well-explained. No need to reinvent the wheel! Here are some pointers.

The solution to the blue eyes puzzle featured on the xkcd website.
The wikipedia article on common knowledge, which uses the blue eyes puzzle as an illustrative example.
A post on the math stackexchange site that gives a detailed an formal proof of result.

The puzzle of the pirate booty

Today’s puzzle was posed on the Riddler blog, but it’s actually a classic among problem-solving enthusiasts, and is commonly known as the pirate game. Here is the formulation used in the Riddler:

Ten Perfectly Rational Pirate Logicians (PRPLs) find 10 (indivisible) gold pieces and wish to distribute the booty among themselves.

The pirates each have a unique rank, from the captain on down. The captain puts forth the first plan to divide up the gold, whereupon the pirates (including the captain) vote. If at least half the pirates vote for the plan, it is enacted, and the gold is distributed accordingly. If the plan gets fewer than half the votes, however, the captain is killed, the second-in-command is promoted, and the process starts over. (They’re mutinous, these PRPLs.)

Pirates always vote by the following rules, with the earliest rule taking precedence in a conflict:

Self-preservation: A pirate values his life above all else.

Greed: A pirate seeks as much gold as possible.

Bloodthirst: Failing a threat to his life or bounty, a pirate always votes to kill.

Under this system, how do the PRPLs divide up their gold?

Extra credit: Solve the generalized problem where there are P pirates and G gold pieces.

Here is the solution to the main problem:
[Show Solution]

This problem is a perfect example of when to use recursion. If there are $P$ pirates, when each pirate contemplates how to vote, they are comparing what would happen if they voted yes (and agreed to the current proposal) to what would happen if they voted no (and the current pirate died, reducing to the $P-1$ case).

Let’s start with two pirates and build up from there. For each case, here is a list of each pirates’ share of the gold. We ordered the pirates from lowest rank to highest rank (captain).

\begin{align}
&\quad\text{Gold distribution} &\text{Votes}&\text{ needed}\\ \hline
v_2 &: \begin{bmatrix} 0 & 10 \end{bmatrix} && 1\\
v_3 &: \begin{bmatrix} 1 & 0 & 9 \end{bmatrix} && 2\\
v_4 &: \begin{bmatrix} 0 & 1 & 0 & 9 \end{bmatrix} && 2\\
v_5 &: \begin{bmatrix} 1 & 0 & 1 & 0 & 8 \end{bmatrix} && 3\\
v_6 &: \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & 8 \end{bmatrix} && 3\\
v_7 &: \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 7 \end{bmatrix} && 4\\
v_8 &: \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & 1 & 0 & 7 \end{bmatrix} && 4\\
v_9 &: \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 6 \end{bmatrix} && 5 \\
v_{10} &: \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 6 \end{bmatrix} && 5
\end{align}

Let’s examine this table one row at a time. If there are two pirates ($v_2$), a majority is decided by a single vote. Since the captain gets to vote, they can safely propose to keep all the gold.

If there are three pirates ($v_3$), a majority is decided by two votes. So the captain needs to secure one extra vote. The first pirate (lowest rank) won’t win anything if the captain dies, because we would reduce to the $v_2$ case. The captain must give this pirate at least one gold piece to buy their vote and avoid death, but can keep the remaining $9$ pieces.

Similarly, if there are four pirates ($v_4$), a majority is decided by two votes. This time, the first pirate’s vote costs two gold pieces because they stand to win one gold piece if we reduce to $v_3$. However, the second pirate’s vote now costs one gold piece because they win nothing in the $v_3$ case. A similar argument applies as we continue to add pirates.

The final solution is that if we number the pirates $1,2,\dots,10$ in order from lowest rank to highest rank, then pirates $2,4,6,8$ each get one gold piece and the captain gets $6$ gold pieces.

And here is a solution to the general case:
[Show Solution]

As we saw in the previous solution, it makes sense to recurse on $P$, the number of pirates. If $G$ is the number of gold pieces, the pattern we observed in the simpler case still hold here, and we can continue it until the captain runs out of gold and is no longer able to bribe enough of his fellow pirates. So the table looks like:

\begin{align}
&\quad\text{Gold distribution} &\text{Votes}&\text{ needed}\\ \hline
v_2 &: \begin{bmatrix} 0 & G \end{bmatrix} && 1 \\
v_3 &: \begin{bmatrix} 1 & 0 & G-1 \end{bmatrix} && 2 \\
v_4 &: \begin{bmatrix} 0 & 1 & 0 & G-1 \end{bmatrix} && 2 \\
v_5 &: \begin{bmatrix} 1 & 0 & 1 & 0 & G-2 \end{bmatrix} && 3 \\
v_6 &: \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & G-2 \end{bmatrix} && 3 \\
&\vdots &&\vdots\\
v_{2G+1} &: \begin{bmatrix} 1 & 0 & \dots & 1 & 0 & 0 \end{bmatrix} && G+1\\
v_{2G+2} &: \begin{bmatrix} 0 & 1 & \dots & 0 & 1 & 0 & 0 \end{bmatrix} && G+1
\end{align}

In the last two rows of the table, there are $G$ 1’s. In the case with $2G+2$ pirates, a majority is decided by $G+1$ votes, so the captain wins nothing; they must forfeit all the gold in order to buy the votes necessary to survive. From this point forward, it may seem that if we add any additional pirates, they will be killed because there isn’t enough gold to buy enough votes. However, this isn’t quite the case. Here is what happens if we keep adding pirates:

\begin{align}
&\quad\text{Gold distribution} &\text{Votes}&\text{ needed}\\ \hline
v_{2G+2} &: \begin{bmatrix} 0 & 1 & \dots & 0 & 1 & 0 & 0 \end{bmatrix} && G+1 \\
{\color{red}v_{\color{red} 2\color{red}G\color{red}+\color{red}3}} &: \begin{bmatrix} ? & ? & \dots & ? & ? & ? & ? & {\color{red}0} \end{bmatrix} && \color{red}G\color{red}+\color{red}2 \\
v_{2G+4} &: \begin{bmatrix} 1 & 0 & \dots & 1 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} && G+2 \\
{\color{red}v_{\color{red} 2\color{red}G\color{red}+\color{red}5}} &: \begin{bmatrix} ? & ? & \dots & ? & ? & ? & ? & ? & ? & {\color{red}0} \end{bmatrix} && \color{red}G\color{red}+\color{red}3 \\
{\color{red}v_{\color{red} 2\color{red}G\color{red}+\color{red}6}} &: \begin{bmatrix} ? & ? & \dots & ? & ? & ? & ? & ? & ? & {\color{red}0} & {\color{red}0} \end{bmatrix} && \color{red}G\color{red}+\color{red}3 \\
{\color{red}v_{\color{red} 2\color{red}G\color{red}+\color{red}7}} &: \begin{bmatrix} ? & ? & \dots & ? & ? & ? & ? & ? & ? & {\color{red}0} & {\color{red}0} & {\color{red}0} \end{bmatrix}\hspace{-2cm} && \color{red}G\color{red}+\color{red}4 \\
v_{2G+8} &: \begin{bmatrix} 0 & 1 & \dots & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}\hspace{-2cm} && G+4
\end{align}

Once we get to $P = 2G+3$ pirates, the captain will always be killed (deaths are indicated in red) since there isn’t enough gold to buy the required votes. In the $2G+4$ case, however, the second in command is doomed to die if he votes to kill the captain, so he will vote yes even if offered nothing. This gives the captain a free vote, which is enough to secure the required $G+2$ votes. The captain must make an offer that compares favorably to the $2G+2$ case since the intermediate case $2G+3$ always leads to $2G+2$.

In the $2G+5$ case, none of the pirates have an incentive to keep the captain alive (since everybody will be safe with $P=2G+4$). The same happens with $2G+6$ and $2G+7$. Once we arrive at $2G+8$, three of the pirates are doomed if the captain dies, so they will vote yes even if offered nothing. Once again, this allows the captain to barely survive. This pattern continues, each time doubling the interval length between safe captains.

The solution to the general problem. Number the pirates $1,2,\dots,P$ in order from lowest rank to highest rank. If we have $G$ gold pieces to distribute, then we consider two cases:

If $P \le 2G+2$, then:

If $P$ is odd, pirates $1,3,5,\dots,P-2$ each get one gold piece, and the captain gets the remaining $G-\frac{P-1}{2}$ pieces.
If $P$ is even, pirates $2,4,6,\dots,P-2$ each get one gold piece, and the captain gets the remaining $G-\frac{P-2}{2}$ pieces.

If $P > 2G+2$, then the highest ranked captains will die until there are $P = 2G+2^k$ pirates remaining with $k$ as large as possible. Then:

If $k$ is even, pirates $1,3,5,\dots,2G-1$ each get one gold piece and nobody else gets anything.
If $k$ is odd, pirates $2,4,6,\dots,2G$ each get one gold piece and nobody else gets anything.

In the case where $P \ge 2G+2$, the solution is not unique in the sense that once we arrive at $P=2G+2^k$, there are other admissible ways of dividing up the gold besides the one shown above.

If this sort of problem interests you, I recommend taking a crack at the riddle of the blue-eyed islanders, or the unfaithful husbands. More information here as well.

Baseball division champs

Today’s post is a Riddler problem about baseball, and it goes like this:

Assume you have a sport (let’s call it “baseball”) in which each team plays 162 games in a season. Assume you have a division of five teams (call it the “AL East”) where each team is of exact equal ability. Specifically, each team has a 50 percent chance of winning each game. What is the expected value of the number of wins for the team that finishes in first place?

The problem statement is a bit vague, so we must make some assumptions in order to solve the problem. Our first solution assumes that the win-loss records of the teams are mutually independent.
[Show Solution]

Our independence assumption basically reduces the AL East to a coin-flipping competition: each team flips 162 fair coins and counts the number of Heads obtained. The team with the most heads wins. In our second solution, we take a closer look at this assumption and discuss its validity.

Let’s say there are $m$ teams and each plays $n$ games. Let $Y_k$ be the number of wins obtained by team $k$. We’d like to find the average number of wins obtained by the team with the most wins. In other words, if we define $Y = \max(Y_1,\dots,Y_m)$, we would like to find $\mathbb{E}(Y)$. Note that multiple teams may be tied for first. If $p(y) = \mathbb{P}(Y=y)$ is the probability mass function, we may rewrite our quantity of interest using cumulative distributions (CDFs).

\begin{align}
\mathbb{E}(Y)
&= \sum_{y=0}^n y\, p(y)
= \sum_{y=0}^n \sum_{z=0}^{y-1} p(y)
= \sum_{z=0}^n \sum_{y=z+1}^n p(y) \\
&= \sum_{z=0}^n\left( 1 – \sum_{y=0}^z p(y)\right) \\
&= \sum_{z=0}^n\bigl( 1 – \mathbb{P}(Y \le z)\bigr)
\end{align}

Since $Y$ is the maximum over all $Y_k$, saying that $Y\le z$ is equivalent to $Y_k \le z$ holding for each $k$. Therefore:

\begin{align}
&= \sum_{z=0}^n\bigl( 1 – \mathbb{P}(Y_1 \le z, Y_2 \le z, \dots, Y_m \le z)\bigr) \\
&= \sum_{z=0}^n\bigl( 1 – \mathbb{P}(Y_1 \le z)\mathbb{P}(Y_2 \le z)\cdots\mathbb{P}(Y_m \le z)\bigr) \\
&= \sum_{z=0}^n\bigl( 1 – \mathbb{P}(Y_1 \le z)^m \bigr)
\end{align}

We made use of our independence assumption in the second equality, by stating that the joint cumulative distribution is equal to the product of cumulative distributions. In the third equality, we used the fact that each team has an identical win distribution, so each $\mathbb{P}(Y_k \le z)$ is the same for different $k$.

Since the games played by a particular team are assumed to be independent Bernoulli trials (coin-flips), the probability of a team winning $y$ of its $n$ games has a Binomial distribution with probability mass function $p(y) = {n \choose y} 2^{-n}$. Therefore, we have:

\[
\mathbb{E}(Y) = \sum_{z=0}^n\left( 1 \,-\, \frac{1}{2^{mn}} \left( \sum_{y=0}^z {n \choose y}\right)^m \right) = 88.3942…
\]

Unfortunately, there is no way to simplify the expression further, so the numerical answer you see above is what you get when you substitute $n=162$ games and $m=5$ teams. One can also use the fact that Binomial distributions approach Normal distributions when the number of trials is high. Namely, $B(n,p) \approx \mathcal{N}(np,np(1-p))$. Using this approximation,

\[
\mathbb{E}(Y) = \int_0^\infty \left[ 1 – \left(\frac{2}{n\pi}\right)^{\frac{m}{2}}
\left( \int_{-\infty}^x e^{-\frac{2}{n}\left(y-\frac{n}{2}\right)^2} \mathrm{d}y \right)^m \right] \mathrm{d}x \approx 88.4011
\]

It’s a pretty good approximation to our first solution, but unfortunately not much easier to evaluate! For the curious among you, here is what the distribution of wins of the best team looks like:

This next solution explains how to tackle the more realistic case where the games are not played independently, and explains why the independence assumption is a good one for the AL East.
[Show Solution]

The coin-flipping assumption we previously used allowed for the (unlikely) possibility of all five teams winning all their games. But this isn’t just unlikely, it’s impossible. In reality, some of the teams will play each other, so it’s impossible for every team to win every game. To illustrate this effect, let’s imaging a simpler scenario with only 3 teams, and each team plays 60 games. In the first plot, I use the independent coin-flip assumption. In the second plot, I assume the teams play each other exclusively.

The most notable difference is that in independent case, it’s possible for a team to win the division despite only winning 29 of 60 games. This can’t happen when the teams play each other, since there will always be at least one team that wins at least half of their games. In the first plot, the expected value is $33.27$ while in the second plot it is $34.01$, a little bit larger. This effect diminishes as we add more teams, or if we have an intermediate scenario (e.g. some fraction of games are played within the division while others are treated as independent coin flips).

Will we see a significant effect in the AL East? In a typical 162-game season, each of the five AL East teams plays 19 games against each of the other four teams for a total of 76 games. Out of the remaining 86 games, 66 are against out-of-division opponents and 20 are against out-of-league opponents. It turns out that the additional teams together with the significant proportion of out-of-division games ends up drowning out the difference between both distributions. In other words, the assumption that each team simply flips 162 coins turns out to be a good one.

Here is one possible way to calculate the probabilities in the realistic case that accounts for inter-division games. Let’s suppose team $i$ plays team $j$ a total of $g$ times. Let $X_{ij}$ be the number of games team $i$ wins in that matchup. Then we clearly have $X_{ij} + X_{ji} = g$. Let $Z_i$ be the out-of-division wins acquired by team $i$. Then the total number of wins by each team in the AL East is:

\begin{align}
Y_k &= Z_k + \sum_{i\ne k} X_{ki} \\
&= Z_k + \sum_{i=1}^{k-1} X_{ki} + \sum_{i=k+1}^m X_{ki} \\
&= Z_k + \sum_{i=1}^{k-1} (g\, – X_{ik}) + \sum_{i=k+1}^m X_{ki} \\
\end{align}

So we have expressed $\{Y_1,\dots,Y_m\}$ (which are not independent) in terms of $\{X_{ij} \mid 1 \le i < j \le m\}$ and $\{Z_1,\dots,Z_m\}$, which are now independent. We'll compute the CDF of the maximum of the $Y_k$'s as in the first solution. Using Bayes' theorem, \begin{align} \mathbb{P}(Y \le z) &= \mathbb{P}( Y_1 \le z,\dots, Y_m \le z ) \\ &= \mathbb{P}( Y_k \le z \mid X_{ij}, Y_k ) \prod_{i < j} \mathbb{P}(X_{ij}) \prod_{k=1}^m \mathbb{P}(Z_k) \end{align} Note that $X_{ij} \sim B(g,\tfrac12)$ and $Z_k \sim B(n-(m-1)g,\tfrac12)$ because each team plays $(m-1)g$ in-division games and so the remaining $n-(m-1)g$ games are out-of-division. Define the region: \begin{align} D &= \left\{ (x_{ij},z_k) \,\middle|\, 0 \le x_{ij} \le g,\quad 0 \le z_k \le n-(m-1)g \right\}\\ R(z) &= \left\{ (x_{ij},z_k) \,\middle|\, z_k + \sum_{i=0}^{k-1} (g\, - x_{ik}) + \sum_{i=k+1}^n x_{ki} \le z\,\,\forall k \right\} \end{align} So the distribution we seek is given by: \begin{multline} \mathbb{P}(Y \le z) \\ = \frac{1}{2^{m(n-\frac12 (m-1)g)}} \sum_{(x_{ij},z_k) \in D \cap R(z)} \prod_{i < j} {g \choose x_{ij}} \prod_{k = 1}^m {n - (m-1)g \choose z_k} \end{multline} The region $D\cap R(z)$ is simply a set of linear inequalities, so one could in principle evaluate the above sum. However, in the case of interest, $n=162$, $m=5$, and $g=19$, the sum has an astronomical number of terms, so some approximations are required to get an actual numerical answer in a reasonable amount of time. I'll spare the details, but suffice to say that we obtain a distribution that is virtually identical to the one we found in the first solution. So the coin-flipping assumption turns out to be a good one for the AL East schedule!

Double-counting, Part 2

This post is a follow-up to Part 1, where I talked about the technique of double-counting in the context of proving combinatorial identities. In this post, I’ll show three more identities that can be proven using simple double-counting. Test your skills!

First identity. This is Vandermonde’s Identity.
\[
\sum_{k=0}^p {m \choose k}{n \choose p-k} = {m+n \choose p}
\]

[Show Solution]

Second identity. This is the Christmas Stocking Identity. It is also sometimes called the Hockey-Stick Identity.
\[
\sum_{k=0}^m {n+k \choose n} = {m+n+1 \choose n+1}
\]

[Show Solution]

Third identity. This one looks similar to the first one, but notice that the upper coefficient is varying this time.
\[
\sum_{k=0}^p {k \choose m}{p-k \choose n} = {p+1 \choose m+n+1}
\]

[Show Solution]

Double-counting, Part 1

Double-counting is one of my favorite proof techniques. The idea is simple: count the same thing in two different ways. In this post, I’ll give some examples of double-counting in the context of proving identities involving binomial coefficients, but it’s a very general technique that can be applied to many other types of problems.

Pascal’s identity. The following is known as Pascal’s identity:

\[
{n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}
\]

Of course, Pascal’s Identity can also be proven directly using simple algebra, but there is a nice double-counting alternative. Suppose we have a group of $n$ people, and we’d like to choose a committee of $k$ members. There are $n \choose k$ ways of doing this. Now let’s count the number of committees in a different way. Suppose we pick out one particular person from the group, let’s call her Alice. There are $n-1\choose k-1$ committees that include Alice, because after we’ve included Alice, there are $k-1$ remaining committee members to choose out $n-1$ remaining people. Similarly, there are $n-1\choose k$ committees that exclude Alice, because all $k$ committee members must be chosen out of the remaining $n-1$ people. The total number of committees is equal to the number of committees that include Alice plus the number of committees that exclude Alice, and this completes the proof of Pascal’s Identity.

Binomial theorem. Here is another familiar identity:

\[
{n \choose 0} + {n \choose 1} + \dots + {n \choose n} = 2^n
\]

This identity can be directly obtained by applying the Binomial Theorem to $(1+1)^n$. But once again, we can use a double-counting argument. Suppose we have a group of $n$ people. Let’s count the total number of subsets of this group. One way to count is to realize that there are $n \choose k$ different subsets of size $k$. So the total number of subsets of any size is the sum on the left-hand side of the identity. On the other hand, we can count subsets by looking at each person one at a time. Each person can either be included or excluded in the subset ($2$ possibilities), which yields a total of $2\times 2 \times \dots \times 2 = 2^n$ possible subsets.

Binomial products. This example involves products:

\[
{n \choose s}{s \choose r} = {n \choose r}{n-r \choose s-r}
\]

Consider a group of $n$ people. This time, we count the number of ways of selecting a team of $s$ members, among which $r$ are designated as captains. One way to do this is to start by selecting the team, which can be done in $n \choose s$ ways. For each team, we then select the captains, which can be done in $s \choose r$ ways. The total is therefore ${n \choose s}{s \choose r}$. Another way to count is to start by selecting the captains first, which can be done in $n \choose r$ ways. Then, we must select the rest of the team. There remains $n-r$ people and we must choose $s-r$ to round out the team. So the total count is ${n \choose r}{n-r \choose s-r}$.

This technique of committee selection is very powerful. See if you can figure out how to apply it to the following example!

\[
{n \choose 1} + 2 {n\choose 2} + 3 {n\choose 3} + \dots + n {n \choose n} = n 2^{n-1}
\]

[Show Solution]

For more double-counting problems, check out Part 2!

Monsters’ gems

Once again, The Riddler does not disappoint! This puzzle is about slaying monsters and collecting gems.

A video game requires you to slay monsters to collect gems. Every time you slay a monster, it drops one of three types of gems: a common gem, an uncommon gem or a rare gem. The probabilities of these gems being dropped are in the ratio of 3:2:1 — three common gems for every two uncommon gems for every one rare gem, on average. If you slay monsters until you have at least one of each of the three types of gems, how many of the most common gems will you end up with, on average?

Here is my solution:
[Show Solution]

A simpler problem: coin flips

A popular (and simpler) version of this problem is the following: “I have a coin that comes up heads with probability $p$ and tails with probability $1-p.$ If I flip the coin until I get heads, how many flips will I make, on average?”. The standard approach to solving this problem is to enumerate all the possibilities:

“H” (one flip), probability $p$.
“T,H” (two flips), probability $(1-p)p$.
“T,T,H” (three flips), probability $(1-p)^2p$.
… (and so on)

To get the expected number of flips, you then multiply each number of flips with its associated probability and sum them:

\[
\sum_{k=1}^\infty k (1-p)^{k-1}p
= -p\,\frac{\mathrm{d}}{\mathrm{d}p} \sum_{k=1}^\infty (1-p)^k
= -p\,\frac{\mathrm{d}}{\mathrm{d}p} \left(\frac{1}{p}\right)
= \frac{1}{p}
\]

This is a pretty standard summation, and there are many ways of evaluating it. One particularly nice approach is to use recursion. Let $X$ be the expected number of flips. After we flipped our first coin, if our first flip was H (probability $p$), we stop flipping so there is no additional length added. If our first flip was a $T$ (probability $1-p$), then we will add $X$ more flips on average. Therefore: $X = 1 + p \cdot 0 + (1-p)\cdot X$. Solving for $X$, we find $X = \frac{1}{p}$, as before. This recursive approach works because the stopping criterion (flipping H) does not depend on what our previous flips were.

Back to monster slaying

We’ll use the recursive approach from the coin-flipping problem to solve the monster slaying problem. What makes this version more difficult is that the coin flips are not all independent. In other words, whether we should stop flipping coins (slaying monsters) depends on which types of gems we have accumulated so far. Let’s say the three types of gems are $p, q, r$. I’ll use the same variable names to denote the respective probability of each gem occurring. The first thing to realize is that to count the expected number of $p$’s that occur, it’s equivalent to count the total number of gems that occur and multiply the result by $p$. This follows from linearity of expectation. Specifically, if the sequence of gems has length $n$ and $X_i$ tells us whether gem $i$ is a $p$ or not, we have:

\begin{multline}
\mathbb{E}\left[\sum_{i=1}^n X_i\right]
= \mathbb{E}\left[ \mathbb{E}\left[ \sum_{i=1}^n X_i \,\middle|\, n \right] \right]
= \mathbb{E}\left[\sum_{i=1}^n \mathbb{E}\left[ X_i\,\middle|\, n \right] \right]\\
= \mathbb{E}\left[\sum_{i=1}^n \mathbb{E}\left[ X_i \right]\right]
= \mathbb{E}\left[ np \right]
= p\, \mathbb{E}[ n ]
\end{multline}

We stop collecting gems once we have at least one of each type of gem. We’ll need several variables to properly characterize our current state of gem accumulation. Define the following:

$X$: the expected number gems we’ll collect from now on, assuming we haven’t collected any gems yet (this is $\mathbb{E}[n]$).
$X_p$ (similarly $X_q, X_r$): the expected number gems we’ll collect from now on, assuming our current collection includes at least one $p$ gem.
$X_{pq}$ (similarly $X_{pr}, X_{qr}$): the expected number gems we’ll collect from now on, assuming our current collection includes at least one $p$ gem and at least one $q$ gem.

The expected number of gems we expect to collect in the future depends on type of gem we get first. We can write the following recursion:

\[
X = 1 + p X_p + q X_q + r X_r
\]

In other words, if our first gem was $p$, we can expect $X_p$ subsequent $p$ gems, plus the first one we just collected. In the other cases, for example if the first gem is $q$, then we can expect $X_q$ subsequent $p$ gems. We can write similar recursions for when we’ve collected our first gem:

\begin{align}
X_p &= 1 + p X_p + q X_{pq} + r X_{pr} \\
X_q &= 1 + p X_{pq} + q X_q + r X_{qr} \\
X_r &= 1 + p X_{pr} + q X_{qr} + r X_r
\end{align}

And, recursions for when we’ve collected two different gems:

\begin{align}
X_{pq} &= 1 + p X_{pq} + q X_{pq} + r \cdot 0 \\
X_{pr} &= 1 + p X_{pr} + q \cdot 0 + r X_{pr} \\
X_{qr} &= 1 + p \cdot 0 + q X_{qr} + r X_{qr}
\end{align}

The last three recursions are decoupled. Solving them, we obtain:

\begin{gather}
X_{pq} = \frac{1}{1-p-q} = \frac{1}{r},\quad
X_{pr}=\frac{1}{1-p-r} = \frac{1}{q},\\
X_{qr}= \frac{1}{1-q-r} = \frac{1}{p}
\end{gather}

In the final equalities, we used the fact that $p + q + r = 1$. These results shouldn’t be surprising — once you’ve already obtained at least one $p$ and one $q$, the problem it simply to count how many more flips until you obtain $r$, and this is precisely the coin-flipping problem! Substituting into the previous set of recursions, we obtain:

\begin{gather}
X_p = \frac{1}{1-p}\left( 1 + \frac{q}{r} + \frac{r}{q}\right),\quad
X_q = \frac{1}{1-q}\left( 1 + \frac{p}{r} + \frac{r}{p}\right),\\
X_r = \frac{1}{1-r}\left( 1 + \frac{p}{q} + \frac{q}{p}\right)
\end{gather}

Finally, substitute these findings into the recursion for $X$, and obtain:

\begin{multline}
X = 1 + \frac{p}{1-p}\left( 1 + \frac{q}{r} + \frac{r}{q}\right)
+ \frac{q}{1-q}\left( 1 + \frac{p}{r} + \frac{r}{p}\right) \\
+ \frac{r}{1-r}\left( 1 + \frac{p}{q} + \frac{q}{p}\right)
\end{multline}

We can now substitute the values $p = \frac{1}{2}$, $q = \frac{1}{3}$, and $r = \frac{1}{6}$ and we obtain that the sequence will have expected length $\mathbb{E}[n] = X = \frac{73}{10}$. Therefore, the expected number of common gems is simply $p \,\mathbb{E}[n] = \frac{73}{20}.$

$\displaystyle
(\text{Expected number of common gems}) = \frac{73}{20} = 3.65
$

A more brute-force approach:
[Show Solution]

Yet another solution approach with very nice write-up can be found on Andrew Mascioli’s blog

P(win point)	P(win game)	P(win set)	P(win match)
49%	47.5%	42.9%	36.8%
45%	37.7%	18.5%	4.61%
40%	26.4%	3.65%	0.04%
1%	1.50×10^-7	2.35×10^-39	1.30×10^-115

A note on interpretations

Even number of sides

Odd number of sides

Calculating the area

Pretty pictures

The fair case

The unfair case

But but but…

A simpler problem: coin flips

Back to monster slaying