This week’s Riddler Classic is Squid Game-themed!

There are 16 competitors who must cross a bridge made up of 18 pairs of separated glass squares. Here is what the bridge looks like from above:

To cross the bridge, each competitor jumps from one pair of squares to the next. However, they must choose one of the two squares in a pair to land on. Within each pair, one square is made of tempered glass, while the other is made of normal glass. If you jump onto tempered glass, all is well, and you can continue on to the next pair of squares. But if you jump onto normal glass, it will break, and you will be eliminated from the competition.

The competitors have no knowledge of which square within each pair is made of tempered glass. The only way to figure it out is to take a leap of faith and jump onto a square. Once a pair is revealed — either when someone lands on a tempered square or a normal square — all remaining competitors take notice and will choose the tempered glass when they arrive at that pair.

On average, how many of the 16 competitors will make it across the bridge?

Here is my solution.

[Show Solution]

Let’s consider a more general version of the game. Let $f(n,m)$ to be the expected number of competitors that make it across the bridge assuming there are $n$ total competitors and the bridge has $m$ unknown tiles remaining. If there are no competitors, then clearly none can make it across. Also, if there are no unknown tiles remaining, then all competitors make it through. This leads to the boundary conditions

\begin{align}

f(0,m) &= 0\quad\text{for }m=0,1,2,\dots \\

f(n,0) &= n\quad\text{for }n=0,1,2,\dots

\end{align}Now consider the general case with $n$ competitors and $m$ bridge tiles. Each time a competitor takes a turn, they will cross some number of tiles before they are eliminated. Let’s look at the possible cases for the first competitor.

- With probability $1/2$, they are eliminated on the first tile. So the $n-1$ remaining competitors only have to contend with $m-1$ unknown tiles.
- With probability $1/4$, they are eliminated on the second tile. So the $n-1$ remaining competitors only have to contend with $m-2$ unknown tiles.
- Continuing in this fashion, with probability $1/2^m$, they are eliminated on the last (the $m^\text{th}$) tile, and the $n-1$ remaining competitors have $0$ unknown tiles to deal with.
- Finally, with the remaining probability of $1/2^m$, the competitor guesses all tiles correctly, which means that all $n$ competitors will get across safely.

We can express these statements concisely in the following recursion.

\[

f(n,m) = \sum_{k=1}^m \frac{1}{2^k} f(n-1,m-k) + \frac{n}{2^m}

\]One way to simplify this expression is to multiply both sides by $2^m$ and define $g_n(m) := 2^m f(n,m)$. Then, the recursion becomes

\begin{align}

g_0(m) &= 0 \\

g_n(m) &= n + \sum_{k=0}^{m-1} g_{n-1}(k)\quad\text{for }n=1,2,\dots

\end{align}Applying this recursion for the first several steps, we obtain

\begin{align}

g_1(m) &= 1\\

g_2(m) &= 2+m\\

g_3(m) &= \tfrac{1}{2}(6+3m+m^2)\\

g_4(m) &= \tfrac{1}{6}(24+14m+3m^2+m^3)\\

g_5(m) &= \tfrac{1}{24}(120+70m+23m^2+2m^3+m^4)\\

g_6(m) &= \tfrac{1}{120}(720+444m+120m^2+35m^3+m^5)\\

g_7(m) &= \tfrac{1}{720}(5040+3108m+1024m^2+135m^3+55m^4-3m^5+m^6)\\

g_8(m) &= \dots

\end{align}From there, we can recover the expected number of winners via $f(n,m) = g_n(m) /2^m$. Although computing each subsequent function is straightforward, I could not find a closed-form expression for $g_n(m)$. Each is a polynomial of degree $n-1$, but beyond some obvious observation such as the constant term being $n$ and the common denominator being $(n-1)!$, I couldn’t find a general formula.

For the specific instance ($n=16$ and $m=18$) described in the problem statement, we can obtain the exact expected number of winners, and it is

$\displaystyle

f(16,18) = \frac{458757}{65536} = 7.0000762939453125 \text{ (exact)}

$

which is slightly larger than $7$.

### Approximate (asymptotic) solution

We can approximate $f(n,m)$ as follows. Each tile will eliminate on average $\frac{1}{2}$ of a contestant. So if we start with $n$ contestants, roughly $n-\frac{1}{2}m$ contestants will cross the bridge. This leads to the approximation

$\displaystyle

f(n,m) \approx n-\tfrac{1}{2}m

$

This approximation doesn’t work when the number of contestants is small. For example, if $n\lt \frac{1}{2}m$, it would lead to a negative number of contestants crossing the bridge, which is of course impossible. But the approximation turns out to be pretty good when $n$ is larger. Applying the approximation to the specific instance in the problem statement, we find $f(16,18) \approx 16-\tfrac{1}{2}\cdot 18 = 7$, and this is *very* close to the true solution!

Here are some plots that confirm the formula; I plotted $f(n,m)$ for fixed values of $n$ and $m$.

And here is a much better solution!

[Show Solution]

This solution comes courtesy of comments by Guy D. Moore and MarkS.

As in the previous solution, suppose we have $n$ contestants and $m$ bridge tiles. Suppose $b$ tiles are broken during the course of the game. This occurs with probability $\frac{1}{2^m}\binom{m}{b}$, since each tile has a probability of $\frac{1}{2}$ of being guessed incorrectly. When $b$ tiles are broken, $n-b$ contestants cross the bridge. Finally, we can break at most $\min(n,m)$ tiles, since there are only $m$ tiles, and each of the $n$ players can break at most one tile. Therefore, the expected number of competitors to make it across the bridge is:

$\displaystyle

f(n,m) = \frac{1}{2^m}\sum_{b=0}^{\min(n,m)} \binom{m}{b}(n-b)

$

If the special case where $n\geq m$, the sum will go up to $m$, and we can evaluate it exactly, by writing:

\begin{align}

(1+x)^m &= \sum_{b=0}^m \binom{m}{b} x^{m-b} \\

x^{n-m}(1+x)^m &= \sum_{b=0}^m \binom{m}{b} x^{n-b} \\

(n-m)x^{n-m-1}(1+x)^m + m x^{n-m}(1+x)^{m-1} &= \sum_{b=0}^m \binom{m}{b} (n-b)x^{n-b-1}

\end{align}where in the last step, we differentiated both sides with respect to $x$. Now, setting $x=1$ on both sides and dividing by $2^m$, we obtain:

\[

\frac{1}{2^m}\sum_{b=0}^m \binom{m}{b} (n-b) = n-\frac{1}{2}m

\]So the “asymptotic” solution I found in my first solution isn’t just asymptotic; it’s exact when $n\geq m$.

When $n\lt m$, there is no closed-form expression for the sum. However, we can be smart about how we evaluate it. Since we know the sum of all $m$ terms, we only have to evaluate $\min(n,m-n)$ terms. This leads us to the complete solution:

$\displaystyle

f(n,m) = \begin{cases}

n-\frac{1}{2}m & \text{if }n \geq m \\

\frac{1}{2^m}\sum_{b=0}^n \binom{m}{b} (n-b) & n\lt m\\

n-\frac{1}{2}m-\frac{1}{2^m}\sum_{b=n+1}^m \binom{m}{b} (n-b) & n \lt m\text{ (alt.)}

\end{cases}

$

### Interesting side-note

Guy D. Moore also pointed out that there is a simpler recurrence relation for $f(n,m)$, given by:

\[

f(n,m) = \frac{f(n,m-1) + f(n-1,m-1)}{2}

\]Using this recurrence with the generating function

\[

G(x,y) = \sum_{n=0}^\infty \sum_{m=0}^\infty f(n,m) x^n y^m,

\]it is possible to show that:

\[

G(x,y) = \frac{x}{(1-x)^2}\cdot \frac{2}{2-y(x+1)}

\]Therefore, $f(n,m)$ is the coefficient corresponding to the $x^n y^m$ term in the series expansion of $G(x,y)$ above! Here is an example of this working for $n=16$ and $m=18$ (as in the original problem) using WolframAlpha.

Hi Laurent,

A nice solution, just two quick comments.

You can make the recursion tighter by considering a single jump.

If there are n competitors and m bridge segments, and the next competitor jumps, either

s/he survives, leaving n competitors and m-1 segments, or

s/he dies, leaving n-1 and m-1: each has equal probability, so

f(n,m) = ( f(n,m-1) + f(n-1,m-1) )/2

The second comment is that the approximate solution is exact for n >= m;

each segment kills on average 1/2 competitor, so f(n,m) = n-m/2.

If n is almost m, you can find the (small) chance that the bridge “would have killed” n+1, n+2, …

and add the number of competitors who weren’t killed because they weren’t there to kill;

for the stated problem, there is a 1/2^18 chance that the bridge “could have killed” 18,

and an 18/2^18 chance that it “could have killed” 17, so the average number to survive is

7 + (18-16) * 1/2^18 + (17-16) * 18/2^18 = 7 + 5/2^16 which is the answer you find.

Nice. That gives me enough hints for a closed-form solution. Let P be the number of players and S the number of segments (because n and m are too hard for me to remember which is which!). Suppose, at the end of the competition, every segment has been hit by at least one player. (If this is not the case, then no player has made it across.) Suppose B segments broke, and S-B did not. The probability of this outcome is C(S,B)/2^S, where C(S,B)=S!/(B!(S-B)!). Each broken segment eliminated exactly one player, so the number of players who made it across is P-B. To get the expected number, we weight by the probability and sum over B from zero to the smaller of P and S. For P>=S, this indeed yields P-S/2, and 7 + 5/2^16 in the case of S=18, P=16.

Thank you both for your comments! I updated my solution to include a “closed-form” solution, with attribution. I also found a generating function for $f(n,m)$, although it’s not particularly insightful.

A little late to this. I don’t have anything more elegant to add to the solutions given but did want to share a very elementary (and computationally tractable) way to compute the expectation.

– The kth person survives if fewer than k tiles are broken: call this p_k

– The expected number of survivors can be written as the sum of indicator variables of the kth person surviving for k = 1, ..n.

– So the expected number of survivors is sum p_k