The Squiddler, 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$ additional rounds, on average, than I’d expect from starting with $N$ people.”

What is the value of $N$?

In the extra-credit version of Mingle, we again 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. In this version, it is even easier to believe this, since rather than unceremonious death, let's say that all contestants in Extra Credit Mingle get paid proportionally for the number of rounds lasted, so that everyone is incentivized for someone to last to the next round.

The extra credit wrinkle of only ever needing to make groups of size $1$ to $10$ introduces some very weird behavior. For instance, if we ever had $N = 2520 = \textsf{lcm} \{ 1, 2, \dots, 10 \}$ then the game will go on for an infinite number of rounds, since no matter what number is called, the contestants will be able to make appropriately round groups. Thus, while there is a nonzero expectation for the number of rounds in the Extra Credit Mingle for $N \lt 2520,$ for any $N \geq 2520$ the expected number of rounds is infinite.

Anyway, let's set up the conditional expectation chain. Let's say that for some $N,$ we know that $E_N$ is the expected number of rounds when starting with $N$ contestants. From the law of total probability, assuming that we know $E_k$ for all $k = 1, \dots, N,$ we can set up the following recursive formula: $$E_N = 1 + \sum_{i=1}^{10} \mathbb{P} \{ i \} E_{ i \lfloor N / i \rfloor } = 1 + \frac{1}{10} \sum_{i=1}^{10} E_{i \lfloor N / i \rfloor}, \,\, \text{for $N \lt 2520$}.$$ (Note, and last one, sorry, but I just think it's kinda neat ... that we see here in the case of $N=2520$ that since $i\lfloor N / i\rfloor = N$ for each $i = 1, \dots, 10,$ that we get the nonsensical $E_{2520} = 1 + E_{2520}.$)

Now there are a few ways to think about this. We can turn the recursion formula into a giant system of linear equations and then solve the $500 \times 500$ lower $10$-diagonal matrix inverse to solve the values of $E_N,$ $N = 1, \dots, 500.$ Instead, I opted for setting up a memoized recursive function in a few lines of Python:

from math import floor
exp_num_rounds = {}
def compute_exp_num_rounds(N):
    if N == 0: return 0
    if N not in exp_num_rounds.keys():
        transitions = []
        for i in range(10):
            transitions.append( int((i+1) * floor( N / ( i+ 1.0) )) )
        others = sum([ compute_exp_num_rounds(t) for t in transitions if t < N ])
        self = sum([ 1 for t in transitions if t == N])
        exp_num = (1.0 + 0.1 * others)/(1.0 - 0.1 * self)
        exp_num_rounds[N] = exp_num
    return exp_num_rounds[N]

Using this function I quickly calculated $E_N$ for $N = 1, \dots, 500,$ and in fact for all $N$ up to $2519.$ We find what looks from a distance as a relatively straight line with a few barely discernable jumps. If we plot the differences $E_{N+1} - E_N$ versus $N$ we see that there are only $9$ total values of the $N$ in $\{1, \dots, 2519\}$ such that the number of expected rounds would be more than $9$ more if they started with $N+1.$ Conveniently, enough, since there is only one such value of below $500$, we know that Young-il is upset that they are starting the round of Extra Credit Mingle with $N=359$ contestants.

Looking at the values with large jump sizes, we can start to build a theoretical argument for why these values exhibit this behavior. Note that in each of these cases, $$N \in \{ 359, 719, 839, 1079, 1259, 1439, 1679, 1799, 2159\}$$ that we have $i \not\mid N$ for each $i = 2, 3, \dots, 10$ while there is only one value of $j \in \{ 2, 3, \dots, 10 \}$ for which $j \not\mid N+1.$ In a sufficiently handwavy way, this relative $9:1$ ratio in probability of dropping below $N$ after round one, is what is driving the roughly $9$ to $10$ additional expected rounds.

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

Ruffles have maximally aligned ridges

Two large planar sheets have parallel semicircular cylindrical ridges with radius $1.$ Neighboring ridges are separated by a distance $L \geq 2$. The sheets are placed so that the ridges extrude toward each other, and so that the sheets cannot shift relative to each other in the horizontal direction, as shown in the cross-section below:

Which value of $L$ maximizes the empty space between the sheets?

Firstly, let's establish some parameters in order to make sure we can turn this into a nice(r) optimization problem. Let $h$ be the vertical distance between the two planar sheets for a given value of $L \geq 2$. Let's assume that one cylindrical ridge on the lower sheet is centered at the origin, that is, $x = 0.$ By construction, the next cyliindrical ridge on the lower sheet (to the right) is centered at $x = L$ and the center of the semicircular cylindrical ridges on the upper sheet that is tangent to these two lower ridges should be centered at $x = \frac{L}{2}.$ Adding in the vertical axis, we have semicircles of radius $1$ centered at $(0,0)$, $(L, 0)$ and $(\frac{L}{2}, h).$

Let's next determine the objective function for optimization, in terms of $h$ and $L$. That is, we are trying to determine the maximal value of the cross-sectional area of empty space per unit length of one sheet. That is, we have $f(h, L) = \frac{A(h,L)}{L},$ where $A(h,L)$ is the cross-sectional area of the empty space bounded by the rectangle $0 \leq x \leq L$ and $0 \leq y \leq h.$ Now, the non-empty space in this rectangle is half of the unit semicircle centered at (0,0), the entire unit semicircle centered at (L/2, h) and half of the unit semicricle centered at (L, 0), so we need to subtract out the total non-empty area of $\pi,$ that is, $A(h,L) = hL - \pi,$ so we arrive at $$f(h, L) = \frac{A(h, L)}{L} = \frac{hL - \pi}{L} = h - \frac{\pi}{L}.$$

Now, let's determine the height $h$ as a function of $L,$ that is, $h = h(L).$ Since there is no ability to shift the sheets horizontally, it must be that the semicircle centered at $(\frac{L}{2}, h(L))$ is tangent to both of the lower semicircles. Thus, we can draw a straight line from $(0,0)$ to $(\frac{L}{2}, h(L))$ which must have length $2$, since each of the semicircles have unit radii, thus we have the Pythagorean theorem $$2^2 = \left(\frac{L}{2}\right)^2 + h(L)^2,$$ or equivalently $$h(L) = \frac{1}{2} \sqrt{16 - L^2}.$$ In actuality, we should be careful to make sure that the space between the sheets is at least the unit radius of the semicircular ridges, that is, $$h(L) = \max \left\{ 1, \frac{1}{2} \sqrt{16 - L^2} \right\}.$$ However, we can disregard the case where $L \gt 2\sqrt{3}$ where $h(L) = 1 \gt \frac{1}{2} \sqrt{16-L^2}$, since otherwise, barring some extreme static friction, we could horizontally shift the sheets relative to one another which is a no-no of the setup.

Having decided to ignore the other case, we have $h(L) = \frac{1}{2} \sqrt{16-L^2}$ for all $2 \leq L \leq 2\sqrt{3},$ so we now have $$f(L) = f(h(L), L) = \frac{1}{2} \sqrt{16 - L^2} - \frac{\pi}{L}.$$ Taking derivatives, we $$f^\prime(L) = \frac{-L}{2 \sqrt{16-L^2}} + \frac{\pi}{L^2},$$ which if we set equal to zero and solve for $L$ results in the sextic polynomial $$L^6 - 4\pi^2 L^2 + 64 \pi^2 = 0.$$ If we set $\ell = L^2,$ then the condition for optimality becomes a depressed cubic in $\ell$ with a single real zero, that can be handled by Cardano's formula, that is, $$\ell = \sqrt[3]{ 32 \pi^2 + \sqrt{ 1024 \pi^4 + \frac{64}{27} \pi^6} } + \sqrt[3]{ 32\pi^2 - \sqrt{1024 \pi^4 + \frac{64}{27} \pi^6}} \approx 7.06550552638\dots$$ Therefore, the optimal spacing of the ridges is $$L^* = \sqrt{\ell} \approx 2.65810186531\dots.$$