Last time I analysed the bridge-crossing scenario in the series Squid Game. In this fictional challenge called “Glass Stepping Stones”, the front contestant must leap forward along glass panels, choosing left or right each time, knowing only that one side is strengthened glass while the other will shatter. At least later players may learn from the choices of their forerunners. Here I use combinatorial arguments, derive a recurrence relation for the chance to die on a given step, and obtain an analytic solution with a hypergeometric function.
Again, write or equivalently P(i,n) for the probability the ith player is still alive on the nth step. We showed these probabilities satisfy the recurrence relation , along with initial conditions , and for all players after the first. Equivalently, we can start from , and for . This is a bit like Pascal’s triangle. Rather than adding the previous two terms, we take their average — which of course is the sum divided by two. And rather than 1’s at the sides, we have 0’s and 1’s.
Let’s write for the likelihood the ith player will die upon landing on the nth step. Then . These values satisfy the same recurrence relation as before:
Only the initial conditions are different: , and for all players after the first. It is aesthetic to begin a step earlier: , except for . The Table below shows a few early entries.
step:
n = 1 |
2 | 3 | 4 | 5 | 6 | 7 | 8 | |
player:
i = 1 |
1/2 | 1/4 | 1/8 | 1/16 | 1/32 | 1/64 | 1/128 | 1/256 |
2 | 0 | 1/4 | 1/4 | 3/16 | 1/8 | 5/64 | 3/64 | 7/256 |
3 | 0 | 0 | 1/8 | 3/16 | 3/16 | 5/32 | 15/128 | 21/256 |
4 | 0 | 0 | 0 | 1/16 | 1/8 | 5/32 | 5/32 | 35/256 |
5 | 0 | 0 | 0 | 0 | 1/32 | 5/64 | 15/128 | 35/256 |
6 | 0 | 0 | 0 | 0 | 0 | 1/64 | 3/64 | 21/256 |
Alternatively, there are elegant combinatorial arguments, for which I was initially inspired by another blog . For player i to die on step n, the previous i – 1 players must have died somewhere amongst the n – 1 prior steps. There are “n – 1 choose i – 1″ ways to arrange these mistaken steps, out of total combinations of equal probability. Given any such arrangement, the next player has a 50% chance their following leap is a misstep, hence:
(I originally found this simple formula in a much more roundabout way, as often happens!) If i > n, the probability is zero. By similar reasoning, the chance that precisely i players have died by step n (inclusive) is:
A draft paper (Henle+ 2021 ) gives this result. It may also be obtained by summing over the previous formula: . Note if player i died on n′, the next player must make n – n′ correct guesses in a row, so that no-one else dies by the nth step.
Now the probability the ith player is alive at the nth step or further, is the probability any number of previous players died by step n or before. (So what is ruled out is i or more dying by this stage.) This is just a sum over the previous displayed formula: , which computer algebra simplifies to:
Here is called the “(ordinary) hypergeometric function”. I gave a limited table of these probability values in the previous blog. For fixed integer , the entire expression reduces to a polynomial in n of order i – 1 with rational coefficients, all times . For example the likelihood the 5th player is alive at step n is:
In general, for n < i we have , so players get some steps for free. The diagonal terms are . This makes sense because for player i to not be alive on the ith step, every leap by previous players must also have been a misstep. Some results like these may also be shown using induction and the recurrence relation. I give more special cases in the next blog post. Yet the general formula works even for non-integers, though this is not physical, as the Figure below shows. For negative parameters (not shown) it has a rich structure, with singularities, and some probabilities values negative or exceeding 1.
An alternative derivation of the probabilities is based on where the previous player died (if at all). If that player i – 1 died on step n′ < n, their follower must make n – n′ correct guesses in a row to reach step n safely. Now sum the result from n′ = i – 1, which is the earliest step upon which they may conceivably die, up to n′ = n – 1. Add to this the chance the player was still alive at step n – 1 (which is one minus the sum of chances they died on step n′) as this guarantees the following player i is alive at n. Numerical testing shows the result is indeed equivalent. Hence rather than summing over players for a fixed step, one may instead sum over steps for a fixed player.