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

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]