Can You Survive Squid Game (Season 2)?

In “Mingle,” $N$ contestants play $38$ rounds. In round $k$ everyone must form groups of exactly $k$; anyone left over is eliminated. What is the smallest $N$ for which at least one contestant can survive all $38$ rounds?

The Fiddler, Zach Wissner-Gross, January 10, 2025(original post)

Solution

Playing to save as many as possible, a count $c$ entering round $k$ leaves $\lfloor c/k\rfloor\cdot k$ survivors. Round $1$ keeps everyone, so the survivors evolve as $c\mapsto\lfloor c/k\rfloor k$ for $k=2,3,\dots,38$, and we need the final count to be at least $1$ (hence at least $38$, a full last group). Searching upward, the smallest starting value that never collapses is $$N=\boxed{454},$$ which finishes with exactly $38$ survivors (the trajectory ends $\dots,170,140,108,74,38$).

The computation

Run the elimination itself: from each starting $N$, apply $c\mapsto\lfloor c/k\rfloor k$ round by round and reject any $N$ whose count ever hits zero. The first survivor is $454$.

def survives(N):
    c = N
    for k in range(2, 39):
        c = (c // k) * k
        if c == 0: return False
    return c >= 1
N = 1
while not survives(N): N += 1
print(N)                                  # 454

Extra Credit

Now each round’s group size is drawn uniformly and independently from $1$ to $10$, and the game runs until no one survives. For some $N<500$, starting with $N+1$ people instead of $N$ lengthens the expected game by about $10$ rounds. Which $N$?

Solution

Let $E(c)$ be the expected number of remaining rounds from $c$ contestants. Conditioning on the group size $g$, and noting $g=1$ (and any $g\mid c$) leaves the count unchanged, $$E(c)=\frac{10+\sum_{g:\;\lfloor c/g\rfloor g\neq c}E\!\bigl(\lfloor c/g\rfloor g\bigr)}{10-\#\{g:\lfloor c/g\rfloor g=c\}}.$$ Evaluating bottom-up, the jump $E(N{+}1)-E(N)$ is about $10$ at exactly one place: $$N=\boxed{359},\qquad E(360)-E(359)\approx 9.94.$$ The reason is arithmetic: $360$ is divisible by nine of the ten group sizes (all but $7$), so it sails through most rounds intact, whereas $359$ is prime and collapses almost at once. (The official value is paywalled; this is my own, by the recursion above.)

The computation

Build $E(c)$ bottom-up straight from the recurrence (each $c$ depends only on strictly smaller counts), then scan for the largest one-person jump.

E = [0.0] * 501
for c in range(1, 501):
    k = sum(1 for g in range(1, 11) if (c // g) * g == c)
    s = sum(E[(c // g) * g] for g in range(1, 11) if (c // g) * g != c)
    E[c] = (10.0 + s) / (10 - k)
print(max(range(1, 500), key=lambda N: E[N + 1] - E[N]))   # 359