Squid game

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$.

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.