The Squiddler

N.B. - Shout-out to colleague and fellow Fiddler enthusiast, Rohit Jawle, for the punny post name this week.

In Season 2 of Squid Game, contestants play a game of “Mingle” (spoiler alert!). For each round of this game, the contestants all wait in a common area until a number is called. They must then split up into groups of that number. Any contestants not in a group of the correct number after $30$ seconds … well, let’s just say bad things happen to them. For now, we’ll refer to contestants who make it through a round in a group of the correct size as having “survived” the round.

Suppose there are initially $N$ contestants. In the first round, contestants must form groups of 1. Okay, that’s not too hard; everyone survives. In the second round, contestants must form groups of $2.$ This continues (with groups of $k$ in round $k$) until the $38$th round, when contestants must form groups of $38.$ What is the smallest number $N$ such that there is at least one person who survives all $38$ rounds?

Let's firstly assume that the contestants are all genial, cooperative mathematicians, and there will me no nefarious and/or inadvertent issues with people not being able to form the appropriate groups of the appropriate sizes. This might not totally make sense in Squid Game context where the penalty for being the odd person out is so draconian as death, but perhaps everyone agreed on an inherent numbering ahead of time, and if your number just doesn't come up in one round or another, these astute and honorable mathematicians at least march to their demise knowing that they played the game optimally. Whatever that's worth.

Anyway ... Let's say that at the end of round $k$ there are $N_k$ contestants remaining. Since any stragglers who are not neatly aligned in a group of $k+1$ at the end of $30$ seconds will be eliminated at the end of round $k+1$, then we see that we must have $$N_{k+1} = (k+1) \left\lfloor \frac{N_k}{k+1} \right\rfloor,$$ where we start with let's say $N_0 = N$ contestants. In theory, we could start at the beginning and guess numbers, work $38$ times through this recursion formula and then see if we end up with anyone remaining after $38$ rounds. Then once we found some starting $N$ that works, for instance, starting $N=2025$ leaves $1634$ lucky remaining contestants after $38$ rounds, you can whittle that down to final a minimal number. Of course, we could also work backwards from the condition that we want to have $N_{38} \gt 0.$

In particular, since we need $N_{38} \gt 0$ and $N_{38} \in 38 \mathbb{Z},$ the minimal number we can have is $N_{38} = 38.$ From the recursion formula, we see that $$38 \left\lfloor \frac{N_{37}}{38} \right\rfloor = 38,$$ which implies that we are looking for $N_{37} \in \{ 38, 39, \dots, 75 \}.$ Since we must also have $N_{37} \in 37 \mathbb{Z},$ we get the minimal value of $N_{37} = 74.$ In turn, we see that $N_{37} = 74$ implies that we must have $N_{36} \in \{ 74, 75, \dots, 110 \} \cap 36 \mathbb{Z},$ that is $N_{36} = 108.$ We can follow all of these nested implications back up to the minimal number of contestants needed to have some number of survivors in each of the 38 rounds to be $N = N_1 = N_2 \geq 454$ contestants. For completeness, if we were to start with $N = 454$ contestants, then the sequence of contestants remaining after $k$ rounds would be as follows:

Round #	Contestants Remaining
0	454
1	454
2	454
3	453
4	452
5	450
6	450
7	448
8	448
9	441
10	440
11	440
12	432
13	429
14	420
15	420
16	416
17	408
18	396
19	380
20	380
21	378
22	374
23	368
24	360
25	350
26	338
27	324
28	308
29	290
30	270
31	248
32	224
33	198
34	170
35	140
36	108
37	74
38	38