Squid Game Bridge: Calculating Survival Odds

Ahead of the players is the Squid Game Bridge with 18 steps, each made of a pair of glass tiles: one of them can hold the weight of a player, while the other can’t.

Players advance on the bridge in a predetermined order, one pair of tiles at a time.

If they choose a solid tile, they advance, otherwise, they are eliminated.

What is the expected number of survivors in a 16-player game?

Introduction:

Let’s try and understand the limitations of the game better. We have to assume that all the players are rational and with perfect memory. This supposition helps us establish that once a player reveals the correct step in a pair, everyone else will remember it. The correct tile can be discovered either by choosing it or by elimination if the wrong one is selected.

Now we look at some possible scenarios under which the game can unfold.

For all the players to survive, we need the first one to make all the correct guesses. This adds up to eighteen 50/50 correct guesses. This scenario has a probability of $\dfrac{1}{2^{18}}$ .

For fifteen players to survive, then only the first one can lose the game. Consider that he gets eliminated on step number i. This means i-1 correct guesses, one wrong guess; Then the following player will have to make 18-i correct guesses. For each value of ‘i’, this probability is $\dfrac{1}{2^{18}}$ .

The most unfortunate case is the one in which no one wins this game. This can happen if every single player makes a wrong choice. Given that there are more steps than players, some players can also make correct guesses before the wrong one. The number of correct guesses in the entire game must be less than three.

Solution:

Let’s formalize all of this. Let X be a Random Variable counting the number of survivors. We want to compute the Expectation of X, and for this, we need the probability that X takes the value ‘i’, with ‘i’ between 1 and 16.

From the previous analysis, we know that:

– The probability of X equals 16 is $\dfrac{1}{2^{18}}$ ;

– The probability of X equals 15 can be computed as the sum of the probability that the first player is eliminated, over all possible places where this happens. Each term is $\dfrac{1}{2^{18}}$ , and we have 18 possible choices (18 choose 1) for that tile.

Now we can generalize this formula to any number of survivors between 1 and 16.

If X equals ‘i’, then 16-i players were eliminated. This gets us to the probability that X equals ‘i’ to be $\dfrac{1}{2^{18}}$ times 18 choose 16-i, which can be seen as 18 choose i+2 times $\dfrac{1}{2^{18}}$ .

For example, the scenario in the series where there were three survivors has a probability of around 3%.

Now we plug everything into the expectation formula.

At this point, you can put this formula in a calculator and get a result, but let’s try and break this down further. For this, we will use the following property:

To prove this, we employ the Binomial Formula for $(x+1)^n$ .

We differentiate with respect to x and replace x with 1 in the final formula.

Getting back to the expectation formula, we write ‘i’ as $i+2 - 2$ and distribute the two terms. Now we want to separate everything into two easier-to-compute parts.

To compute A, we first rewrite the sum by replacing $i+2$ with ‘j’ and then expanding it to the formula we derived earlier and applying it.

For B, we apply the same replacement of $i+2$ by j and expand the sum.

In the end, we replace A and B in the expectation formula and get that expectation of X is $7 + \dfrac{20}{2^{18}}$ .

In an interview setting, this would be the end of this question. With access to a computer, we can use a generalized formula to plot the distribution of survival probabilities for different numbers of tiles.

Alongside this, we can also compute the expected number of winners of this game for different path lengths.

Simulation:

For this simulation we will use a single external python library:

random – We will use the random choice function to determine if a player picks the correct tile

Implementation logic: we will use the same simplified problem as above, all players have perfect memory and play perfectly in order. We can thus simplify the problem, imagining that they all move together, advancing to the end. A successful step increases the counter of steps discovered, while a wrong one removes a player.

Putting it all together:

 import random
 
 def sim_game(no_players, no_steps):
    end = 0
    for i in range(1,no_players+1):
        for j in range(0,no_steps):
           if random.choice([0,1])>0:
                end += 1
                if end >= no_steps:
                    return no_players+1-i
            else:
                end += 1
                if end >= no_steps:
                    return no_players-i
                break
    return 0