Riddler – Page 2 – Book Proofs

Knocking down the last bowling pin

This week’s Riddler classic is a tough one! Here is a paraphrased version of the problem.

Imagine $n^2$ bowling pins arranged in a rhombus. The image to the right illustrates the case $n=3$. We knock down the topmost pin. When any pin gets knocked down, each of the (up to two) pins directly behind it has a probability $p$ of being knocked over (independently of each other). We are interested in the probability that the bottommost pin gets knocked down in the limit of large $n$.

The original problem specifically asked about $p=0.5$ and $p=0.7$.

My solution:
[Show Solution]

Let $F(n,p)$ be the probability that the bottommost pin gets knocked over. The problem asks about $\lim_{n\to\infty} F(n,0.5)$ and $\lim_{n\to\infty} F(n,0.7)$.

Percolation theory

This problem is closely connected to a topic in statistical physics called percolation theory. Statistical physics is concerned with how microscopic properties (e.g., how atoms interact with their neighbors) can lead to macroscopic properties, such as temperature, phase (liquid, solid, gas), and more. We can reframe the problem in statistical physics terms by thinking of the bowling pins as atoms in a porous material. At the microscopic scale, water can squeeze through the space between molecules with probability $p$. Beneath each space, there are two spaces in the next layer. Then, we can ask whether water can percolate through the material or not. In other words, we are asking the macroscopic question: Is the material waterproof?

To get a feel for this, let’s run some simulations. We’ll start with $p=0.5$ and $n=20$. Here, the topmost pin is in the top left, and the bottommost pin is in the bottom right. We can see that the pins never really get rolling because the probability $p$ is too small. In this case, there is no percolation.

Now let’s increase the probability to $p=0.7$. For these plots, I zoomed out and used $n=100$. We can see that in most of the cases, the floodgates open and a large number of pins get knocked down (percolation!). But it doesn’t happen every time. Some cases still run into bad luck and get stopped before the chain reaction can develop.

In percolation theory, the scenario we’re studying is called “directed bond percolation on a 2D square lattice”. It is directed because the pins can only knock other pins over in one direction (downwards), and it is bond percolation because each link (bond) in the lattice is active with probability $p$, as opposed to site percolation where all links are active, but you make a particular pin active with probability $p$.

A fundamental result in percolation theory is that there is a critical probability $p_c$ at which percolation begins to happen. In other words, the probability of percolation $\theta(p)$ satisfies:
\[
\theta(p) \begin{cases}
=0 & \text{for }0 \leq p \lt p_c \\
\gt 0 & \text{for }p_c \lt p \leq 1
\end{cases}
\]The exact value of $p_c$ is only known for certain special cases. For example, it was proved in the following seminal paper that if you have an infinite square lattice and allow pins to knock each other down in all 4 directions, the critical probability is exactly $1/2$:

Harry Kesten. “The Critical Probability of Bond Percolation
on the Square Lattice Equals 1/2”. Commun. Math. Phys. 74, 41-59 (1980). A pdf of this manuscript is freely available here.

The case of directed bond percolation on a square lattice (which is our case of interest) is still an open problem. We know some bounds, however. For example, it was derived in various papers that
\[
0.5176 \leq p_c \leq 0.6298
\]Why is this relevant? Well the problem asks about the cases $p=0.5$ and $p=0.7$, which lie conveniently outside these bounds! Therefore,

When $p=0.5$, the bound above tells us that $p < p_c$. Therefore, $\theta(0.5)=0$ and we have no percolation. So, the probability of knocking over the bottommost pin when $n$ is large is zero.
When $p=0.7$, the bound above tells us that $p > p_c$. Therefore, $\theta(0.7) > 0$ and we have percolation. So, there is a nonzero probability that we will knock over the bottommost pin when $n$ is large.

An analytic lower bound

Given that finding the exact value of $p_c$ is still an open problem, it seems hopeless to look for an analytic solution to the original question involving the bottommost pin. However, we can use an analytic approach to get a bound that allows us to confirm the result for $p=0.5$.

Let’s count the total number of paths that connect the topmost pin to the bottommost pin. Each path consists of $2(n-1)$ steps, and exactly half of the steps are “left” and the other half are “right”. They can be in any order, so the total number of distinct paths is $\binom{2n-2}{n-1}$. Each path also has a probability $p^{2n-2}$ of occurring, since each link has a probability $p$ of being active. Therefore,
\begin{align}
&\mathrm{Prob}(\text{at least one active path})\\
&= 1-\mathrm{Prob}(\text{no active path}) \\
&= 1-\mathrm{Prob}\left(\text{path }k\text{ is inactive for }k=1,\dots,\textstyle\binom{2n-2}{n-1}\right) \\
&\leq 1-\prod_{k=1}^{\binom{2n-2}{n-1}} \mathrm{Prob}(\text{path }k\text{ is inactive}) \\
&=1-\left(1-p^{2n-2}\right)^{\binom{2n-2}{n-1}}
\end{align}Here, the inequality follows from the fact that the paths are not mutually independent (they may have edges in common), and the lower bound comes from assuming independent paths. As an example, suppose there are two paths, and $A$ and $B$ are the events that the paths are inactive, respectively. Then, the probability that $A$ is inactive increases if we know that $B$ is inactive (because the paths may have edges in common). This means that:
\[
P(A\cap B) = P(A\mid B)P(B) \geq P(A)P(B)
\]Note that we have equality if $A$ and $B$ are independent (the paths share no edge in common). Consequently, we now have an analytic upper bound on the probability we care about:

$\displaystyle
F(n,p) \leq 1-\left(1-p^{2n-2}\right)^{\binom{2n-2}{n-1}}
$

Let $L$ be the limit as $n\to\infty$. We can evaluate it as follows:
\begin{align}
L &= 1-\lim_{n\to\infty} \left(1-p^{2n-2}\right)^{\binom{2n-2}{n-1}} \\
&= 1-\lim_{m\to\infty} \left(1-p^{2m}\right)^{\binom{2m}{m}} \\
&= 1-\exp\,\lim_{m\to\infty} \binom{2m}{m} \log \left(1-p^{2m}\right) \\
&= 1-\exp\,\lim_{m\to\infty} \frac{2^{2m}}{\sqrt{m\pi}} \log \left(1-p^{2m}\right) \\
&= 1-\exp\,\lim_{m\to\infty} \frac{4^{m+1} \sqrt{m}\, p^{2 m} \log (p)}{\sqrt{\pi } \left(1-p^{2 m}\right) (m \log (16)-1)} \\
&= 1-\exp\,\lim_{m\to\infty} \frac{4 \cdot (2p)^{2m} \log (p)}{ \log (16)\sqrt{m\pi} } \\
&= 1-\exp\begin{cases}
0 & \text{for }0 \leq p \leq \frac{1}{2}\\
-\infty & \text{for }\frac{1}{2} < p \leq 1 \end{cases}\\ &= \begin{cases} 0 & \text{for }0 \leq p \leq \frac{1}{2}\\ 1 & \text{for }\frac{1}{2} < p \leq 1 \end{cases} \end{align} In the fourth step, we used an asymptotic approximation for the binomial coefficient. In the fifth step, we used L’Hôpital’s rule. Putting everything together, the upper bound on our probability of interest in the limit of large $n$ allows us to conclude that

$\displaystyle
\lim_{n\to\infty} F(n,p) = 0
\quad\text{for } 0 \leq p \leq \frac{1}{2}.
$

So we can answer part of the problem analytically: when $p\leq 0.5$, we can never knock over the bottommost pin in the limit of very large $n$.

Simulation results

To precisely pinpoint the probability of interest in the case $p>0.5$ requires more work, and here we turn to simulation. The first simulation I produced is intended to illustrate the behavior of $F(n,p)$ as $n$ grows.

Here, we can see that for $p \leq 0.5$, the probability of knocking over the bottommost pin clearly tends to zero, as we predicted. Moreover, for $p \geq 0.7$, the probability appears to tend to a constant value, again as predicted. The intermediate cases ($p=0.55, 0.60, 0.65$) are ambiguous, and it isn’t clear whether the limit is zero or if it tends to a positive constant. Note: The slight wiggles in the plot lines are due to the inherent randomness in the simulations. Each point is an average of $50{,}000$ simulations.

The second simulation I ran looked at the limiting probability only, by computing $F(n,p)$ for a large value of $n$. Here, I used $n=300$ and $10{,}000$ simulations per point. Here, we can clearly see the phase transition, which occurs near $p=0.6$. It is difficult to estimate exactly where the transition occurs because this is similar to estimating $p_c$. The closer we get to the critical probability, the longer our typical paths become. So it is not clear which paths are percolating because we’re not using a sufficiently large $n$ to see the true behavior.

Based on the plot, we can see that $\lim_{n\to\infty} F(n,0.7) \approx 0.58$. In order to get more accuracy, I computed how many simulations I would need to run in order to get more accuracy. Using the confidence interval for a Bernoulli process, we can show that an error of $\pm 0.001$ with $95\%$ confidence requires about $1{,}000{,}000$ simulations. This led me to the following slightly more accurate result.

$\displaystyle
\lim_{n\to\infty} F(n,0.7) \approx F(300,0.7) \approx 0.5782 \pm 0.001.
$

Can you keep your marbles?

This week’s Riddler classic is a logic problem.

There are four enormous bags of marbles. They are labeled RED, GREEN, BLUE, and ASSORTED. You want to buy two bags of marbles that are not assorted, and you’d settle for some combination of red, green or blue. However, someone switched around the labels on all four bags so that every single bag is incorrectly labeled. You may sample two marbles out of any of the bags, one at a time. Is there a picking strategy that guarantees that you will buy two non-assorted bags?

My solution:
[Show Solution]

How high should you climb up the tower?

This week’s Riddler classic is a neat geometry problem.

Two people climb two of the tallest towers on an planet, which happen to be in neighboring cities. You both travel 100 meters up each tower on a clear day. Due to the curvature of the planet, they can barely make each other out. The first person returns to the ground floor of their tower. How high up their tower must the second person be you can barely make each other out again?

My solution:
[Show Solution]

Suppose the planet has radius $r$. Assuming the planet is a perfect sphere, when both people are 100 meters above ground, the line connecting them must be tangent to the sphere. This produces an isosceles triangle. When the first person goes to the bottom of their tower, we obtain a right-angle triangle. Here is a picture of what this might look like, for a planet with radius $r\approx 1000\,\text{m}$, here is what the picture looks like. We can see the height we seek (shown in red) is about 530 meters.

But this isn’t the whole story. The answer depends on the planet’s radius! Here is what we get when we use a larger radius or a smaller radius:

It appears that the larger the radius of the planet, the smaller the red height (HG). Let’s figure out the exact answer in terms of the radius. Looking at triangle $OEC$, we see that
\[
\cos(\theta) = \frac{OE}{OC} = \frac{r}{r+100}
\]Now looking at triangle $OBG$, we see that
\[
\cos(2\theta) = \frac{OB}{OG} = \frac{r}{r+x}
\]where $x$ is the unknown height we seek. Substituting these expressions in the the double-angle cosine identity $\cos(2\theta)=2\cos^2(\theta)-1$, we obtain:
\[
\frac{r}{r+x} = 2\left(\frac{r}{r+100}\right)^2-1
\]Solving for $x$, we obtain:

$\displaystyle
x=HG = \frac{400r^2+20000r}{r^2-200r-10000}
$

Here is what this function of $r$ looks like when plotted:

The vertical asymptote occurs when $r=100(1+\sqrt{2}) \approx 241.42$. This is the point at which the two towers are at 90 degrees to each other. In this case, when the first person goes the the bottom of their tower, their line of sight is parallel to the other tower, so the other tower will never be visible, no matter how tall it is!

The horizontal asymptote occurs in the limit $r\to\infty$, which leads to a height of 400 meters. So in the limit of a large planet, this is what we can expect to see. We can also develop an asymptotic approximation by expanding as a series about $r=\infty$. This leads to:
\[
x = 400+\frac{10^5}{r} + O(r^{-2})
\]

For some context, the Earth has a radius of $6.371\times 10^6$ meters. Using this value of $r$, we find height of $x\approx 400.01569671$. Using the approximation with the extra $r^{-1}$ term, we obtain $x\approx 400.01569612$, which is correct to nine significant figures!

Tower of goats

This week’s Riddler classic is a counting problem. Can the goats fit in the tower?

A tower has 10 floors, each of which can accommodate a single goat. Ten goats approach the tower, and each goat has its own (random) preference of floor. Multiple goats can prefer the same floor. One by one, each goat walks up the tower to its preferred room. If the floor is empty, the goat will make itself at home. But if the floor is already occupied by another goat, then it will keep going up until it finds the next empty floor, which it will occupy. But if it does not find any empty floors, the goat will be stuck on the roof of the tower. What is the probability that all 10 goats will have their own floor, meaning no goat is left stranded on the roof of the tower?

My solution:
[Show Solution]

Suppose there are $n$ goats and the building has $n$ floors. Let $a_i$ be the floor preference of goat $i$, with $i=1,\dots,n$. We will say a vector of floor preferences $v=(a_1,a_2,\dots,a_n)$ is “crowded” if it leads to exactly one goat on each floor.

Let $f(n)$ be the number of crowded floor preferences. Since there are $n^n$ total possible preference vectors (each of the $n$ goats can prefer $n$ different floors), the probability that each goat finds a floor is $f(n)/n^n.$ Therefore, solving the problem amounts to finding $f(n)$.

The following elegant counting argument is due to Pollak (1974). We start by considering a modified version of the problem:

Add one extra floor (the roof). The goats are allowed to pick this $(n+1)^\text{st}$ floor as their preferred floor.
Just like the other floors, the roof can accommodate at most one goat.
If a goat ends up on the roof and there is no space for it, the goat “wraps around”; it takes the elevator back down to the first floor and continues its search for an open floor.

In our modified version of the problem, each goat will eventually occupy a floor (possibly the roof), and there will be exactly one empty floor. If the empty floor is the roof, then no goat had the roof as its preferred floor, no goat ever visited the roof, and no goat ever had to take the elevator back down. Therefore, the vector of floor preferences was crowded according to our original definition. Conversely, if one of the other floors ends up empty, then a goat ended up on the roof, which means the original vector of floor preferences was either invalid (one of the goats picked the roof), or the preferences were valid but a goat nonetheless overflowed onto the roof.

So not only is $f(n)$ equal to the number of crowded preference vectors in the original problem, it is also equal to the number of preference vectors in the modified problem that lead to the roof being empty.

The final piece to this argument is to realize that there must be an equal number of preference vectors that lead to the $k^\text{th}$ floor being empty, for $k=1,\dots,n+1$. This follows because of the symmetry in the modified version of the problem. Specifically, if a particular preference vector $(a_1,\dots,a_n)$ leads to floor $k$ being empty, then $(a_1+j,\dots,a_n+j)$ leads to floor $k+j$ being empty (where we wrap all numbers around so they are in the range between $1$ and $n+1$).

Since there are $(n+1)^n$ total possible preference vectors for the modified problem (each of the $n$ goats can prefer $n+1$ different floors), and there are $n+1$ possible empty floors, we obtain
\[
f(n) = \frac{(n+1)^n}{n+1} = (n+1)^{n-1}
\]Converting this number into a probability as explained at the beginning of the solution, we find that the probability that $n$ goats have a crowded set of preferences is

$\displaystyle
p(n) = \frac{(n+1)^{n-1}}{n^n} = \frac{1}{n+1}\left(1+\frac{1}{n}\right)^n
$

For the case $n=10$, we can calcluate:
\[
p(10) = \frac{11^9}{10^{10}} = \frac{2{,}357{,}947{,}691}{10{,}000{,}000{,}000} \approx 23.58\%
\]

Since $\lim_{n\to\infty} \left(1+\frac{1}{n}\right)^n = e$, it follows that in the asymptotic limit of large $n$, we have $p(n) \sim \frac{e}{n+1}$. Here is a plot comparing the true probability to this asymptotic approximation.

About this problem’s history

This sort of counting problem, where you start with a preference and move to the next available open slot, is also known as a parking problem, because its original formulation was about cars trying to park on a one-way street and taking the next available open spot. There are many other equivalent counting problems, which you can find more about in the entry A000272 in the Online Encyclopedia of Integer Sequences. For a wonderful explanation of the parking problem and other related counting problems, take a look at Richard Stanley’s slides on the topic. The solution in my post above is based on the argument in Richard’s slides, which is due to Pollak (1974).

Catch the grasshopper

This week’s Riddler classic is a probability problem about a grasshopper!

You are trying to catch a grasshopper on a balance beam that is 1 meter long. Every time you try to catch it, it jumps to a random point along the interval between 20 centimeters left of its current position and 20 centimeters right of its current position. If the grasshopper is within 20 centimeters of one of the edges, it will not jump off the edge. For example, if it is 10 centimeters from the left edge of the beam, then it will randomly jump to anywhere within 30 centimeters of that edge with equal probability (meaning it will be twice as likely to jump right as it is to jump left). After many, many failed attempts to catch the grasshopper, where is it most likely to be on the beam? Where is it least likely? And what is the ratio between these respective probabilities?

My solution:
[Show Solution]

Let’s suppose the beam has length $L$ and the grasshopper can jump a maximum distance $\frac{M}{2}$. Define $p(x)$ to be the probability density function describing how likely the grasshopper is to be at any given location $x\in\left[-\frac{L}{2},\frac{L}{2}\right]$.

We can arrive at $p(x)$ via a sequential process. Suppose that at time $k$, the grasshopper has distribution $p_k(x)$. When the grasshopper jumps, its probability distribution becomes $p_{k+1}(x)$. Our goal is to find the limiting distribution $p = \lim_{k\to\infty} p_k$.

At each step, the grasshopper’s density function gets convolved with an appropriate uniform distribution corresponding with where it might land. We can write this as:
\[
p_{k+1}(x) = \int_{-L/2}^{L/2} \Psi(x,y) p_k(y) \,\mathrm{d}y.
\]Here, for each $y$, the kernel $\Psi(x,y)$ is the density function (of $x$) corresponding to a uniform distribution between $\max\bigl(-\frac{L}{2},y-\frac{M}{2}\bigr)$ and $\min\bigl(\frac{L}{2},y+\frac{M}{2}\bigr)$, since this corresponds to the range of locations a grasshopper at location $y$ can jump to. Putting all this together, we get the formula:
\[
p_{k+1}(x) = \int_{\max\bigl(-\frac{L}{2},x-\frac{M}{2}\bigr)}^{\min\bigl(\frac{L}{2},x+\frac{M}{2}\bigr)} \frac{p_k(y)\,\mathrm{d}y}{\min\bigl(\frac{L}{2},y+\frac{M}{2}\bigr)-\max\bigl(-\frac{L}{2},y-\frac{M}{2}\bigr)}.
\]Yuck! To get a better handle on what this might look like, we can simulate it using the given problem parameters ($L=1$ and $M=0.4$) using units of meters. Here is what we obtain when recursively apply the above formula, assuming $p_0$ is a uniform distribution:

The steady-state distribution is the same no matter what we use as the starting distribution. Here is what it looks like when we start the grasshopper on the left edge of the beam. I had to use different axis scaling to make the transient behavior fit in the plot, but the limiting distribution in the same:

These simulations give us a big hint: The limiting distribution appears to be piecewise-linear! We already expected a symmetric distribution due to the symmetry in the problem, but now we can posit a density function of the form:
\[
p(x) = \begin{cases}
ax+b & -\frac{L}{2}\leq x \leq -\left|\frac{L-M}{2}\right| \\
c & -\left|\frac{L-M}{2}\right| < x < \left|\frac{L-M}{2}\right| \\ -ax+b & \left|\frac{L-M}{2}\right| \leq x \leq \frac{L}{2} \end{cases} \]We have three unknown parameters $(a,b,c)$, so we need three equations. First, $p$ is a probability density, so $\int_{-L/2}^{L/2}p(x)\,\mathrm{d}x=1$. Second, $p$ is continuous at the boundaries $x=\pm \left|\frac{L-M}{2}\right|$. Finally, we must satisfy $p(x) = p_{k+1}(x) = p_k(x)$ in the original recursion in our original recursion. Solving these equations, we find three cases: \[ p(x) = \begin{cases} \begin{cases} \frac{2 (L+M+2 x)}{M (4 L-M)} & -\frac{L}{2}\leq x \leq \frac{-L+M}{2} \\ \frac{4}{4 L-M} & \frac{-L+M}{2} < x < \frac{L-M}{2} \\ \frac{2 (L+M-2 x)}{M (4 L-M)} & \frac{L-M}{2} \leq x \leq \frac{L}{2} \end{cases} & 0 < M < L \\[3mm] \begin{cases} \frac{2 (L+M+2 x)}{M (4 L-M)} & -\frac{L}{2}\leq x \leq \frac{-M+L}{2} \\ \frac{4 L}{M (4 L-M)} & \frac{-M+L}{2} < x < \frac{M-L}{2} \\ \frac{2 (L+M-2 x)}{M (4 L-M)} & \frac{M-L}{2} \leq x \leq \frac{L}{2} \end{cases} & L < M < 2L \\[3mm] \quad\frac{1}{L} & 2L < M \end{cases} \] We can also calculate the ratio of largest to smallest likelihood in all three cases. The largest likelihood occurs in the center ($x=0$) while the smallest occurs at an edge ($x=\pm\frac{L}{2}$). We then obtain: \[ \frac{p_\text{max}}{p_\text{min}} = \begin{cases} 2 & 0 < M < L \\[1mm] \frac{2L}{M} & L < M < 2L \\[1mm] 1 & 2L < M \end{cases} \] So, amazingly, the ratio of largest likelihood to the smallest likelihood is 2, a constant indepedent of the length $L$ or the grasshopper range $M$, so long as $M < L$. In particular, the likelihood ratio is $2$ for the setting given in the problem statement ($L=1$ and $M=0.4$).

Desert escape

This week’s Riddler classic is about geometry and probability, and desert escape! Here is the (paraphrased) problem:

There are $n$ travelers who are trapped on a thin and narrow oasis. They each independently pick a random location in the oasis from which to start and a random direction in which to travel. What is the probability that none of their paths will intersect, in terms of $n$?

My solution:
[Show Solution]

First, consider a simpler problem, where all travelers depart from the same side of the oasis. Here is a diagram of what that might look like.

The paths will not cross precisely if the angles from left-to-right are arranged from smallest to largest. For example, in the diagram above, the paths will not cross because $\theta_1 \lt \theta_2 \lt \theta_3$. Once you fix the angles, only one of the $n!$ possible arrangements of the travelers will have the correct ordering. Therefore, the probability that the paths do not intersect is $\frac{1}{n!}$.

Now consider the case where travelers can depart from either side of the oasis. Suppose $k$ travelers depart from the top and $n-k$ depart from the bottom, as in the diagram below.

Since each traveler is equally likely to depart from either side, the probability of this happening is $\frac{1}{2^n} \binom{n}{k}$ (it’s a binomial distribution). The probability that the paths do not intersect is $\frac{1}{k!(n-k)!}$, since it is the product of the probability that the $k$ travelers departing from the top do not intersect and the $n-k$ travelers departing from the bottom do not intersect, and both events are independent. To find the total probability $P_n$, we sum over all possible $k$:
\begin{align}
P_n &= \frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} \frac{1}{k!(n-k)!} \\
&= \frac{1}{2^n \cdot n!} \sum_{k=0}^n \binom{n}{k} \frac{n!}{k!(n-k)!} \\
&= \frac{1}{2^n \cdot n!} \sum_{k=0}^n \binom{n}{k} \binom{n}{n-k} \\
&= \frac{1}{2^n \cdot n!}\binom{2n}{n} \\
&= \frac{(2n)!}{2^n \cdot (n!)^3}
\end{align}The last step is a result of Vandermonde’s identity. You can think of it as counting the number of ways of picking $n$ objects from a set of $2n$ objects. We can do this by imagining that our $2n$ objects are split into two groups of $n$, and we are picking $k$ from the first group and $n-k$ from the second group, and then summing over $k$. If you are interested in these sorts of binomial identities, I encourage you to read the two-part blog post I wrote on the topic (part 1 and part 2). So when the dust settles, the probability of the paths not intersecting is:

$\displaystyle
P_n = \frac{(2n)!}{2^n \cdot (n!)^3}
$

This function decreases rapidly as $n$ increases. To see this, we can plot $P_n$ as a function of $n$. Here is what we obtain:

To get a better handle on $P_n$, we can use Stirling’s approximation to the factorial, $n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$, which yields
\[
P_n \sim \frac{1}{2\sqrt{2}\,\pi\,e} \left( \frac{2e}{n}\right)^{n+1}
\]This tells us that $\log(P_n) \sim -n\log(n)$, which agrees with the almost linear decrease of $P_n$ on a log scale.

Tetrahedral dice game

This week’s Riddler Classic is a game of four-sided dice:

You have four fair tetrahedral dice whose four sides are numbered 1 through 4.

You play a game in which you roll them all and divide them into two groups: those whose values are unique, and those which are duplicates. For example, if you roll a 1, 2, 2 and 4, then the 1 and 4 will go into the “unique” group, while the 2s will go into the “duplicate” group.

Next, you reroll all the dice in the duplicate pool and sort all the dice again. Continuing the previous example, that would mean you reroll the 2s. If the result happens to be 1 and 3, then the “unique” group will now consist of 3 and 4, while the “duplicate” group will have two 1s.

You continue rerolling the duplicate pool and sorting all the dice until all the dice are members of the same group. If all four dice are in the “unique” group, you win. If all four are in the “duplicate” group, you lose.

What is your probability of winning the game?

My solution:
[Show Solution]

We can view this game as a Markov chain. At any point in time, we are in a particular state of the game, and when we re-roll the dice, we transition to a different state. Although there are many possible states (one for each possible way of rolling the four dice), we can use symmetry arguments to reduce the total states to just four. Here they are:

All dice are duplicates. This includes cases like (1,1,1,1) but also (2,2,3,3). If we ever arrive at this position, the game ends and we lose.
Three dice are duplicates. For example: (1,1,1,2)
Two dice are duplicates. For example: (1,1,2,3)
No dice are duplicates. For example: (1,2,3,4). If we ever arrive at this position, the game ends and we win.

We can associate each state transition with a probability. For example, suppose we roll (1,1,2,3). We are in the “two-duplicate” state. We must re-roll the two 1’s, and four things could happen:

We roll (2,2) or (3,3) (probability 1/8). We now have 3 duplicates and the game continues.
We roll (2,3) or (3,2) (probability 1/8). We now have 4 duplicates and the game ends (we lose).
We roll (1,4) or (4,1) (probability 1/8). We now have no duplicates and the game ends (we win).
We roll anything else (probability 5/8). We have 2 duplicates again and the game continues.

If we continue in this manner and find all possible transition probabilities between all four states, we obtain the following diagram:

We can think of the “three duplicates” state as our start state. Why? Because we start the game by rolling all four dice. This is mathematically equivalent to rolling three dice, since the value of the die we don’t roll might as well have been our first roll (all numbers are equivalent by symmetry). Therefore, we can represent our transitions as follows:
\[
A = \begin{bmatrix}
1 & \frac{5}{32} & \frac{1}{8} & 0 \\
0 & \frac{3}{16} & \frac{1}{8} & 0 \\
0 & \frac{9}{16} & \frac{5}{8} & 0 \\
0 & \frac{3}{32} & \frac{1}{8} & 1
\end{bmatrix},\qquad
x_0 = \begin{bmatrix}
0 \\ 1 \\ 0 \\ 0\end{bmatrix}.
\]Notice that all columns sum to 1 since the sum of probabilities from every node along outgoing edges must sum to 1. We can view our current state distribution as a column vector that sums to 1. For example, our initial state is given by $x_0$ above, since we start in the “three-duplicate” state with probability 1. Every time we transition to a new state, our new distribution can be found by multiplying our current state by $A$. In other words:
\[
x_{k+1} = A x_k,\quad\text{for }k=0,1,\dots
\]The question is: where will we end up on average? This is equivalent to asking for the limit
\[
x_\infty = \lim_{k\to\infty} A^k x_0
\]We can find this limit by performing an eigenvalue decomposition:
\begin{align}
A &= V\Lambda V^{-1} \\
&= \begin{bmatrix}
0 & 1 & \frac{23}{21} & -1 \\
0 & 0 & -\frac{8}{21} & 30 \\
0 & 0 & -\frac{12}{7} & -30 \\
1 & 0 & 1 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & \frac{3}{4} & 0 \\
0 & 0 & 0 & \frac{1}{16}
\end{bmatrix}
\begin{bmatrix}
0 & \frac{9}{20} & \frac{29}{60} & 1 \\
1 & \frac{11}{20} & \frac{31}{60} & 0 \\
0 & -\frac{21}{44} & -\frac{21}{44} & 0 \\
0 & \frac{3}{110} & -\frac{1}{165} & 0
\end{bmatrix}
\end{align}The limit is therefore:
\begin{align}
A^\infty x_0 &= V \Lambda^{\infty} V^{-1}x_0 \\
&= \begin{bmatrix}
0 & 1 & \frac{23}{21} & -1 \\
0 & 0 & -\frac{8}{21} & 30 \\
0 & 0 & -\frac{12}{7} & -30 \\
1 & 0 & 1 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
0 & \frac{9}{20} & \frac{29}{60} & 1 \\
1 & \frac{11}{20} & \frac{31}{60} & 0 \\
0 & -\frac{21}{44} & -\frac{21}{44} & 0 \\
0 & \frac{3}{110} & -\frac{1}{165} & 0
\end{bmatrix} \begin{bmatrix}
0 \\ 1 \\ 0 \\ 0\end{bmatrix}\\
&= \begin{bmatrix}
0 & 1 \\
0 & 0 \\
0 & 0 \\
1 & 0
\end{bmatrix}
\begin{bmatrix}
0 & \frac{9}{20} & \frac{29}{60} & 1 \\
1 & \frac{11}{20} & \frac{31}{60} & 0
\end{bmatrix}
\begin{bmatrix}
0 \\ 1 \\ 0 \\ 0\end{bmatrix} \\
&= \begin{bmatrix}
\frac{11}{20} \\ 0 \\ 0 \\ \frac{9}{20}\end{bmatrix}
\end{align}In other words, there is a 11/20, or 55% chance that we will lose and end up in the “all duplicate” case, and a 9/20, or 45% chance that we will win and end up in the “all unique” case.

Frustrating elevator

This weeks Riddler Express is a problem about a frustrating elevator! Here it goes:

You are on the 10th floor of a tower and want to exit on the first floor. You get into the elevator and hit 1. However, this elevator is malfunctioning in a specific way. When you hit 1, it correctly registers the request to descend, but it randomly selects some floor below your current floor (including the first floor). The car then stops at that floor. If it’s not the first floor, you again hit 1 and the process repeats.

Assuming you are the only passenger on the elevator, how many floors on average will it stop at (including your final stop, the first floor) until you exit?

My solution:
[Show Solution]

Let $a_n$ be the expected number of button presses required to reach floor $1$ when starting at floor $n$. Clearly, we have $a_1=0$, and for the other $a_n$, it will take us one button press, plus however many more we accrue at our destination. Since each floor below us is equally likely, this means we have the recursion:
\[
a_{n+1} = 1+\frac{1}{n}\left( a_1+a_2+\cdots+a_n \right)\qquad\text{for }n=1,2,\dots
\]Multiply this by $n$, and write out the equation for two consecutive $n$ values:
\begin{align}
n a_{n+1} &= n + a_1 + a_2 + \cdots + a_n \\
(n-1) a_n &= (n-1) + a_1+ a_2+\cdots + a_{n-1}
\end{align}Now subtract the second equation from the first, and obtain:
\[
n a_{n+1}-(n-1)a_n = 1 + a_n
\]Rearranging and simplifying, we obtain
\[
a_{n+1}=a_n+\frac{1}{n}
\]This nice recursion, together with $a_1=0$, gives us a formula for the expected number of button presses from any floor:

$\displaystyle
a_n = 1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n-1}\qquad\text{for }n=2,3,4,\dots
$

If we start at the 2nd floor, it should take us exactly one button press to reach the first floor, since this is the only place the elevator can take us. The formula confirms that $a_2=1$. If we start at the 3rd floor, the formula says $a_3=1+\frac{1}{2}=\frac{3}{2}$. This also makes sense. Half of the time it will take us 1 press, the other half of the time it takes us 2 presses, and $\frac{3}{2}$ is the average of 1 and 2.

Continuing in this fashion, we can answer the original problem, which is the case $n=10$.
\[
a_{10} = 1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{9} = \frac{7129}{2520} \approx 2.82897
\]

Alternative solution

An alternative solution, courtesy of Ross Boczar, is to derive the recursion more directly using conditional expectation.
\begin{align}
a_{n+1} &= \mathbb{E}( \text{stops if we start at }n+1) \\[2mm]
&= \mathbb{E}(\text{stops}\;|\;\text{didn’t stop at }n)\cdot\mathbb{P}(\text{didn’t stop at }n) \\
&\hspace{2cm} + \mathbb{E}(\text{stops}\;|\;\text{stopped at }n)\cdot\mathbb{P}(\text{stopped at }n) \\[2mm]
&= a_n \left( 1-\frac{1}{n}\right) + \left(1+a_n\right)\frac{1}{n} \\
&= a_n + \frac{1}{n}
\end{align}

Cone crawling

This week’s Riddler Classic is a geometry problem about traversing the surface of a cone

The circular base of the cone has a radius of 2 meters and a slant height of 4 meters. We start on the base, a distance of 1 meter away from the center. The goal is to reach the point half-way up the cone, 90 degrees around the cone’s central axis from the start, as shown. What is the shortest path?

Here is my solution:
[Show Solution]

Suppose the base has radius $r_0$ and we start a distance $\rho_0$ from the center (point $A$). Suppose the slant height is $r_1$ and our goal is to reach a point $\rho_1$ from the top (point $B$). We can break the journey into two parts. No matter how we get from $A$ to $B$, we must reach the edge of the base (point $X$) at some point on our journey. Suppose $X$ is located at an angle $\theta$ from the center of the base.

In the diagram above, we show the 3D cone and the corresponding unfolded 2D version to the right. The corresponding points have matching labels (click the diagram to enlarge) The first part of the journey, from $A$ to $X$, should be a straight line, since this is the shortest distance connecting two points on a flat surface. By the law of cosines, the distance $AX$ is
\[
|AX| = \sqrt{ r_0^2 + \rho_0^2-2r_0\rho_0\cos(\theta) }
\]The second part of the journey, from $X$ to $B$, will be a curved path along the surface of the cone. However, since we want the shortest possible path, this will be a straight line if we unfold the cone. This unfolded cone is a circular sector with radius $r_1$. Based on the diagram below, we can apply the law of cosines again to find the distance $XB$:
\[
|XB| = \sqrt{ r_1^2 + \rho_1^2-2r_1\rho_1\cos(\phi) }
\]But what is $\phi$? The arclengths along the edge of the base for both parts of the path must sum to 90 degrees. So the sum of both arclengths must equal one quarter of the circumference of the base. In other words, the points $X’$ and $R’$ must coincide with $X$ and $R$, respectively, when we fold the cone back together. Therefore,
\[
r_0 \theta + r_1 \phi = \tfrac{\pi}{2}r_0
\]Putting these three ingredients together, our goal is to solve the optimization problem:
\begin{align}
\underset{\theta,\phi}{\text{minimize}} \quad & \sqrt{ r_0^2 + \rho_0^2-2r_0\rho_0\cos(\theta) } + \sqrt{ r_1^2 + \rho_1^2-2r_1\rho_1\cos(\phi) } \\
\text{subject to} \quad & r_0 \theta + r_1 \phi = \tfrac{\pi}{2}r_0 \\
& 0 \leq \theta \leq \tfrac{\pi}{2}
\end{align}

Eliminating $\phi$ from the objective, we can write a single expression for the total distance $f(\theta)$ traveled in terms of the location $\theta$ of the crossover point:
\[
f(\theta) = \sqrt{ r_0^2 + \rho_0^2-2r_0\rho_0\cos(\theta) }
+ \sqrt{ r_1^2 + \rho_1^2-2r_1\rho_1\cos\Bigl[\tfrac{r_0}{r_1}\bigl(\tfrac{\pi}{2}-\theta\bigr)\Bigr] }
\]Here is a plot of what this function looks like when we use the parameters given in the problem statement ($r_0=2$, $\rho_0=1$, $r_1=4$, $\rho_1=2$)

We can see the minimum occurs at around 30 degrees. Next, we will dig a bit deeper and show that the minimum occurs at exactly 30 degrees, and we will derive a solution in the more general case.

General solution

For general values of $(r_0,\rho_0,r_1,\rho_1)$, we can look for a value of $\theta$ that minimizes $f(\theta)$ by taking the derivative and setting it equal to zero. However, the algebra is a bit simpler if we do not eliminate $\phi$ and write down optimality conditions using the method of Lagrange multipliers. Doing this and simplifying, we obtain two conditions:
\begin{gather}
\frac{\rho_0\sin\theta}{\sqrt{ r_0^2+\rho_0^2-2 r_0 \rho_0\cos(\theta)}}
= \frac{\rho_0\sin\phi}{\sqrt{ r_1^2+\rho_1^2-2 r_1 \rho_1\cos(\phi)}}
\\
\theta + \frac{r_1}{r_0} \phi = \frac{\pi}{2}
\end{gather}By the law of sines, the first equation says that $\alpha = \angle OXA = \angle PX’B$. Intuitively, this has the following interpretation: If we imagine rolling one circle around the other until points $X$ and $X’$ coincide, the points $B,X’,X,O$ will all lie on a straight line (the two red segments form a straight line). By writing out the law of sines on the third side, we can obtain slightly simpler expressions now involving $(\theta,\phi,\alpha)$:
\begin{align}
\rho_0 \sin(\theta+\alpha) &= r_0 \sin(\alpha) \\
\rho_1 \sin(\phi+\alpha) &= r_1 \sin(\alpha) \\
\theta + \tfrac{r_1}{r_0}\phi &= \tfrac{\pi}{2}
\end{align}Expanding the first two equations using angle sum identities and eliminating $\alpha$, we obtain an even simpler set of equations:
\[
\frac{\tfrac{r_0}{\rho_0}-\cos\theta}{\sin\theta} = \frac{\tfrac{r_1}{\rho_1}-\cos\phi}{\sin\phi}
\quad\text{and}\quad
\theta + \tfrac{r_1}{r_0}\phi = \tfrac{\pi}{2}
\]This is pretty difficult to solve in general, but certain special cases make things easier. For example, if $\tfrac{r_0}{\rho_0}=\tfrac{r_1}{\rho_1}$, then we must have $\theta=\phi$. This is precisely the case in the problem statement, because we have $\tfrac{r_0}{\rho_0}=\tfrac{r_1}{\rho_1}=2$. Furthermore, we have $\tfrac{r_1}{r_0}=2$, so the second condition becomes $\theta + 2\theta = \tfrac{\pi}{2}$, from which we conclude that $\theta=\tfrac{\pi}{6}=30^\circ$. Substituting back into the formula for total distance, we find the length of the shortest path:

$\displaystyle
\text{Minimum distance} = f\bigl(\tfrac{\pi}{6}\bigr) = 3 \sqrt{5-2 \sqrt{3}} \approx 3.71794
$

So we can find an analytic solution to this problem whenever the start and end points are the same fraction of the way from the centers of their respective circles!

Visualize the vertex

This week’s Riddler Classic is a neat geometry problem about

Suppose you have two distinct points anywhere on the coordinate plane. If I tell you that a parabola with a vertical line of symmetry passes through those two points, where on the plane could that parabola’s vertex be?

Here is my solution:
[Show Solution]

Since the two points can be anywhere, let’s define our coordinate system so that the origin is located at the midpoint between the two points. This way, by symmetry, we can say the two points are located at $A(-u,-v)$ and $B(u,v).$ A parabola with vertical axis of symmetry and vertex located at $(x,y)$ satisfies an equation of the form $v-y=a(u-x)^2$. Given that such a parabola passes through $A$ and $B$, the equation must be satisfied when we substitute the coordinates of $A$ and $B$:
\begin{align}
-v-y &= a(-u-x)^2 \\
v-y &= a(u-x)^2
\end{align}Eliminating $a$ from this pair of equations, we are left with a single equation that relates the coordinates of the vertex $(x,y)$ and the coordinates $u$ and $v$ that determine the locations of $A$ and $B$.
\[
y = \frac{v}{2u}\left( x + \frac{u^2}{x} \right)
\]The set of points $(x,y)$ is a hyperbola centered at the origin (the midpoint of $A$ and $B$), whose asymptotes are the lines $x=0$ and $y=\tfrac{v}{2u}x$. Here is a figure showing the point and the hyperbola corresponding to the locus of possible locations of the vertex.

Geometric visualization

One way to visualize the locus of possible parabola vertex locations is to use the geometric definition of a parabola: A parabola is the set of points equidistant from a point $F$ (the focus) and a line (the directrix). Here is a diagram showing this construction in action:

As $P’$ slides along the directrix, the parabola is the set of points $P$ that are equidistant to the directrix and the point $F$.

In the original problem, we are considering parabolas with a vertical axis of symmetry, therefore the directrix must be horizontal. We can find the location of the focus by drawing circles centered at $A$ and $B$ that are tangent to the directrix, and the focus must be located at an intersection point of the circles. Finally, the vertex of the parabola is the midpoint between the focus and the directrix. As we pick different locations for the directrix, we sweep out all possible locations of the vertices.

In the diagram above, the two possible foci are at $F_1$ and $F_2$, with corresponding vertices $P_1$ and $P_2$, respectively. The associated parabola are shown in violet. As we translate the directrix vertically up and down, the points $P_1$ and $P_2$ trace out the green hyperbola. If you would like to see this for yourself, here is an interactive Geogebra visualization (you can move the directrix or the point $B$). Note: you may need to zoom/pan to see the figure.

If the above applet does not work, try this link.