Can You Survive Another Squid Game?

The final $20$ players of a Squid Game stand in a circle, numbered $1$ to $20$ clockwise. Contestant $2$ is eliminated first. Then the contestant two places clockwise from where $2$ stood, contestant $4$, is eliminated, then contestant $6$, and so on round the circle, which closes up after every elimination. So after contestant $20$ goes, the next to go is $3$, now two places clockwise from where $20$ stood. This continues until one contestant is left. What is the winner’s number?

The Fiddler, Zach Wissner-Gross, July 21, 2023(original post)

The official solution appeared in the post of July 28, 2023 and gives contestant $9$, and for the Extra Credit contestant $18$, with probability $35{,}531/2^{19}$. Both agree with the answers below.

Solution

This is the Josephus problem with every second person removed, and it yields to one observation: a full lap round the circle halves the problem.

With $20$ players, the first lap removes $2, 4, 6, \dots, 20$, every even number. That leaves the ten odd numbers $1, 3, 5, \dots, 19$, and the count resumes from where $20$ stood, so the next to go is $3$, the second of the survivors. That is exactly the original game played on ten people, with the $j$th person in the new circle wearing the number $2j - 1$. Writing $J(n)$ for the position of the winner in a circle of $n$, $$J(2m) \;=\; 2J(m) - 1 .$$ An odd circle, $n = 2m + 1$, works the same way with one extra step. The lap removes $2, 4, \dots, 2m$, and the next count skips $2m + 1$ and removes $1$. The survivors $3, 5, \dots, 2m + 1$ then play the game afresh, the count starting just after $1$, so the $j$th of them wears $2j + 1$, and $$J(2m + 1) \;=\; 2J(m) + 1 .$$ With $J(1) = 1$ these two rules finish the job in four steps: $$\begin{aligned} J(2) &= 2 \cdot 1 - 1 = 1, & J(5) &= 2 \cdot 1 + 1 = 3, \\ J(10) &= 2 \cdot 3 - 1 = 5, & J(20) &= 2 \cdot 5 - 1 = 9 . \end{aligned}$$ $$\boxed{\ \text{contestant } 9 \text{ wins}. \ }$$ Unwinding the rules gives the classical closed form. If $n = 2^a + L$ with $0 \le L < 2^a$, the winner is $2L + 1$: here $20 = 16 + 4$ and $2 \cdot 4 + 1 = 9$. In words, once $L$ people have been removed the circle has a power of two left, and from then on the person about to start each lap, here number $9$, is never touched.

The computation

The check simply plays the game on a list, removing contestants one at a time. It is written for any sequence of steps, so the Extra Credit can reuse it.

from fractions import Fraction
from itertools import product

def play(steps, n=20):
    """Play the game: each step moves that many places
    clockwise from the last elimination and removes the
    contestant there. Returns the winner."""
    circle = list(range(1, n + 1))
    gap = 0              # index of the place just vacated
    for s in steps:
        k = (gap + s - 1) % len(circle)
        circle.pop(k)
        gap = k % len(circle) if circle else 0
        if len(circle) == 1:
            break
    return circle[0]

print("always two places: winner", play([2]*19))

It prints

always two places: winner 9

Extra Credit

Run the game again, but now each move goes two or three places clockwise, chosen at random with equal chances and independently each time. Which contestant is most likely to win?

Solution

The halving trick is gone, because a random step breaks the regular lap. What survives is the idea of relabelling the circle after each elimination.

Describe a circle of $n$ people by numbering them $1, \dots, n$ clockwise starting just after the place where the last elimination happened. A move of $s$ places removes the person numbered $s$ (counting round again if $s > n$, so in a circle of two a move of three removes person $1$). The circle that remains has $n - 1$ people, and renumbering it from just after the removed person sends old number $i$ to new number $i - s$ if $i > s$, and to $i - s + n$ if $i < s$.

Write $r_s(i)$ for that new number. If $P_n(i)$ is the chance that the person numbered $i$ in a circle of $n$ wins, then $P_1(1) = 1$ and $$P_n(i) \;=\; \tfrac12\,P_{n-1}\bigl(r_2(i)\bigr) \;+\; \tfrac12\,P_{n-1}\bigl(r_3(i)\bigr),$$ with a term counted as zero when that move removes $i$. The start of the puzzle is exactly this numbering, with contestant $i$ numbered $i$, so the answer is the largest of $P_{20}(1), \dots, P_{20}(20)$.

The first few circles show how it goes. In a circle of two, a move of two removes person $2$ and a move of three removes person $1$, so each wins with chance $\frac12$. In a circle of three, person $1$ survives either move and then stands in a circle of two, winning with chance $\frac12$; persons $2$ and $3$ each survive one move of the two and win with chance $\frac14$. Each step of the recursion has denominators that double, so after $19$ eliminations every chance is a whole number over $2^{19}$.

Running the recursion up to $n = 20$, by hand in principle and by computer in practice, gives the chart below. The chances climb steadily through the late teens and peak at contestant $18$: $$\boxed{\ \text{contestant } 18, \text{ with probability } \tfrac{35{,}531}{2^{19}} \approx 6.78\%. \ }$$ The value comes from computation rather than a formula; the recursion is what makes it exact. The neighbours are close behind, $19$ at $6.74\%$ and $1$ at $6.24\%$, while $2$ and $3$, the only ones who can go first, are the least likely to win.

The computation

The check does not use the recursion. There are only $2^{19} = 524{,}288$ equally likely sequences of moves, so it plays every one of them with the play function above and counts the winners.

wins = [0]*21
for steps in product((2, 3), repeat=19):   # all 2^19 runs
    wins[play(steps)] += 1
best = max(range(1, 21), key=lambda c: wins[c])
p = Fraction(wins[best], 2**19)
print("most likely winner:", best)
print(f"with probability {p} = {float(p):.4f}")

It prints

most likely winner: 18
with probability 35531/524288 = 0.0678