Book Proofs – Page 15 – A blog for mathematical riddles, puzzles, and elegant proofs

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

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.

Counting parallelograms

The following problem appeared in the 1991 CMO, and it has a particularly clever solution.

In the figure, the side length of the large equilateral triangle is $3$ and $f(3)$, the number of parallelograms bounded by sides in the grid, is $15$. For the general analogous situation, find a formula for $f(n)$, the number of parallelograms, for a triangle of side length $n$.

triangle_lattice

[Show Solution]

Proud partygoers puzzle

Another great problem from the Riddler blog.

A group of N people are in attendance at your shindig, some of whom are friends with each other. (Let’s assume friendship is symmetric — if person A is friends with person B, then B is friends with A.) Suppose that everyone has at least one friend at the party, and that a person is “proud” if her number of friends is strictly larger than the average number of friends that her own friends have. (A competitive lot, your guests.)

Importantly, more than one person can be proud. How large can the share of proud people at the party be?

The solution:
[Show Solution]

The answer is that at most $N-2$ attendees can be proud. To achieve a maximal share of proud people, start with a party where everybody is friends with everybody else and then break one of the friendships. Then, the $N-2$ attendees with intact friendships will be proud and the two attendees with a broken friendship will be non-proud. To show that $N-2$ is really the best we can do, we need to prove that any party must contain at least two attendees that are not proud.

Fact: If an attendee is proud, at least one of her friends must have strictly fewer friends than her. This follows from the definition that an attendee is proud if her number of friends is strictly larger than the average number of friends that her own friends have.

An immediate consequence of the Fact above: in any party, the attendee with the smallest number of friends is always non-proud. And if several attendees share that same minimal number of friends, they are all non-proud. So it’s impossible to have a party where all attendees are proud.

Let’s try to construct a party where $N-1$ attendees are proud. Based on the arguments above, the party must contain a single attendee $A$ that has the minimal number of friends $k$. This will be the non-proud attendee, and all other attendees must be proud. Let $\{B_1,\dots,B_m\}$ be the set of attendees with the second-smallest number of friends, $s > k$.

Since each $B_i$ is proud, they must be friends with $A$. This follows from the Fact above, because the only attendee with fewer friends than $B_i$ is $A$. Therefore, $A$ is friends with every $B_i$. This means $k \ge m$.
Since $s > k$ and $k \ge m$, it follows that $m-1 \le s-2$.

Let’s take a closer look at the $s$ friends of $B_i$.

One of $B_i$'s friends is $A$, who has $k$ friends. Since $s > k$, then $A$ has at least $s-1$ friends.
At most $m-1$ of $B_i$'s friends can be other $B_j$'s, each of which have $s$ friends. However, since $m-1 \le s-2$, this can account for at most $s-2$ of the friends.
At least one more friend is required to make the total of $s$, and this friend is neither $A$ nor a $B_j$. So these remaining friends will each have at least $s+1$ friends.

So the average number of friends of all of $B_i$'s friends is at least:

\[
\frac{1}{s}\bigl( (s-1) + (s-2)s + (s+1) \bigr) = s
\]

If the average number of friends is at least $s$, it cannot be strictly less than $s$, which implies that $B_i$ cannot be proud. In summary, the two least popular attendees at any party must be non-proud. This completes the proof that $N-2$ is the largest share of proud partygoers possible.

A clever integral

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

Evaluate the following definite integral.

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

The solution:
[Show Solution]

Elevator button puzzle

This problem was originally posted on the Riddler blog. Here it goes:

In a building’s lobby, some number (N) of people get on an elevator that goes to some number (M) of floors. There may be more people than floors, or more floors than people. Each person is equally likely to choose any floor, independently of one another. When a floor button is pushed, it will light up.

What is the expected number of lit buttons when the elevator begins its ascent?

My solution:
[Show Solution]

A natural first step is to find the probability that one button will be lit, that two buttons will be lit, and so on. Using all these probabilities, we can then compute the expected number of lit buttons. While it’s possible to solve the problem this way, it turns out to be the path of most resistance. For a single lit button, it’s not too difficult to see that the probability is $ 1/M^{N-1}$. But as we try to count the number of ways that exactly two, or three, or more buttons can be lit, it becomes increasingly difficult to keep track of all the possibilities while avoiding double-counting.

Since the riddle doesn’t ask for individual probabilities, is it possible to calculate the expected number of lit buttons without calculating the individual probabilities? Yes!

Let $P(k,n)$ be the probability that $ k$ lights are off after $ n$ people have pressed a button (we’re counting the number of lights off rather than the number of lights on because it makes the math a little simpler). As mentioned above, these are difficult to compute. As we’ll see, we can solve the problem without ever computing them! Suppose that the $(n+1)$st person now comes along, presses their desired button, and there are now $ k$ lights off. This could have happened in two ways:

$k$ lights were off prior, and the $(n+1)$st button press didn’t change anything. This means one of the $(M-k)$ on-lights was pressed, which would have happened with probability $\frac{M-k}{M}$.
$k+1$ lights were off prior, and the $(n+1)$st button press turned on a light that was previously off. This means one of the $ (k+1)$ off-lights was pressed, which would have happened with probability $\frac{k+1}{M}$.

Therefore, we can write a recursion that describes how the probability changes as more people press a button:

\[
P(k,n+1) = \frac{M-k}{M} P(k,n) + \frac{k+1}{M} P(k+1,n)
\]

What we’re really after is the expected number of lights that are off after $ n$ people have made their selection. We’ll call this quantity $ \theta(n)$. The expected value is obtained by summing up each possible number of lights off, weighed by its corresponding probability. Applying this definition together with the recursion from above, we obtain:

\begin{align}
\theta(n+1) &= \sum_k k P(k,n+1) \\
&= \sum_k k \left( \frac{M-k}{M} P(k,n) + \frac{k+1}{M} P(k+1,n) \right) \\
&= \sum_k \left( k \frac{M-k}{M} P(k,n) + k \frac{k+1}{M} P(k+1,n) \right) \\
&= \sum_k \left( k \frac{M-k}{M} P(k,n) + (k-1) \frac{k}{M} P(k,n) \right) \\
&= \sum_k k \frac{M-1}{M} P(k,n)\\&= \left(1-\frac{1}{M}\right)\theta(n)\\
\end{align}

This recursion tells us how the expected number of lights off changes as more people are added but, amazingly, it does not depend on the individual $ P(k,n)$ probabilities! All lights are off when the elevator is empty, so $ \theta(0) = M$. We conclude that:

\[
\theta(N) = \left( 1-\frac{1}{M} \right) \theta(N-1)
= \dots = \left( 1-\frac{1}{M} \right)^N \theta(0)
= M \left( 1-\frac{1}{M} \right)^N
\]

Finally, the riddle asks for the expected number of lights on, which is $ M$ minus the expected number of lights off. Putting everything together, we obtain the final solution: the expected number of lit buttons is:

$\displaystyle
M\left( 1-\left( 1-\frac{1}{M} \right)^N \right)
$

As a sanity check, note that the formula simplifies to 0 when $ N=0$ and to 1 when $ N=1$, which are the answers we expect. Also, as $ N\to\infty$, the formula asymptotically approaches $ M$, which also makes sense. The formula is valid regardless of whether there are more people than floors or more floors than people.

An interesting fact is that if $ M=N$ (as many people as floors) and we take the limit as the number of floors goes to infinity, the fraction of lit buttons will tend to $ 1-1/e$, which is approximately 63.2%.

A much more elegant solution, courtesy of Ross Boczar
[Show Solution]