This week the question is: Can You Survive Squid Game (Season 2)?

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 38th 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?

And for extra credit:

There are N contestants about to play Mingle, where N is less than 500. This time, in each round, the number for group size can be anywhere from 1 to 10, with each number equally likely to be called. Also, the numbers called in the rounds are all independent of each other. It appears this version of Mingle will continue until there are no more survivors.

Before the game starts, one of the contestants, Young-il, does some quick computation. He says to his companion, Gi-hun: “Oh no, it’s too bad we only have N people.” (Of course, Young-il doesn’t actually say “N,” but rather the number that N represents.)

Young-il continues: “If we had started with N+1 people instead, I’d expect the game to last about 10 more rounds, on average.”

What is the value of N?

Highlight to reveal (possibly incorrect) solution:

Program. A little messy.

If we begin with N persons, before round 1, of course, after round 1 there will be f(1) = N persons. After round 2, we need to take N, divide by 2 to get the number of groups, round down to nearest integer if necessary, and then multiply by 2. f(2) = ⌊ f(1)/2 ⌋ * 2. And it goes on like this: f(3) = ⌊ f(2)/3 ⌋ * 3. In general, after round M we have f(M) = ⌊ f(M-1)/M ⌋ * M.

I wrote a program to calculate f(38), given an N. Some trial and error showed, that given N = 500, f(38) > 0. I then rewrote the program to try all possible N from 1, and stop when f(38) was positive the first time. Solution: we were looking for N = 454.

Just for fun I wrote some more code. Going the opposite direction, we might say f(37) = ⌈ f(38)/37 ⌉ * 37. Basing a small algorithm on this, I got the same solution, but I wasn’t sure that wasn’t luck.

Part 2:

Program. Spreadsheet/PDF.

For this I wrote another program. This one really calls out for some Monte Carlo. Try all N from 1 to 500, simulate X executions, calculate the average length of an execution (how many rounds), run the program, export to csv, open in Libre Office Calc, make an extra column with the difference between lengths for this particular N and the one above, some conditional formatting to look for a difference close to 10, and bam! Just to make sure, I looked a little closer at this neighborhood, and it just became clearer, that I was looking in the right place (see PDF above). The solution is N = 359.

I have a suspicion, this is because 360 is such a nice number. Coming from 361, 362, 363 etc., there’s a good chance of landing here. And then only moving on to a lower number, if the random number is 7.