Can You Survive Another Squid Game?
Outwit. Outplay. Out-calculate.
Welcome to Fiddler on the Proof! The Fiddler is the spiritual successor to FiveThirtyEight’s The Riddler column, which ran for eight years under the stewardship of Zach Wissner-Gross and Ollie Roeder.
Each week, I present mathematical puzzles intended to both challenge and delight you. Beyond these, I also hope to share occasional writings about the broader mathematical and puzzle communities.
Puzzles come out Friday mornings (8 a.m. Eastern time). Most can be solved with careful thought, pencil and paper, and the aid of a calculator. Many include “extra credit,” where the analysis gets particularly hairy or where you might turn to a computer for assistance.
I’ll also give a shoutout to 🎻 one lucky winner 🎻 of the previous week’s puzzle, chosen randomly from among those who submit their solution before 11:59 p.m. the Monday after that puzzle was released. I’ll do my best to read through all the submissions and give additional shoutouts to creative approaches or awesome visualizations, the latter of which could receive 🎬 Best Picture Awards 🎬.
This Week’s Fiddler
This week’s puzzle is an oldie but a goodie, and comes from high school student Meryl Zhang of Plano, Texas, who was named the top math awardee at this year’s Regeneron International Science and Engineering Fair. For her project, Meryl developed novel heuristics for the NP-hard partition problem. Meryl enjoys K-dramas, including Squid Game—a show that has already proven ripe for riddles.
This week, the final 20 players in the Squid Game competition form a circle and are assigned the whole numbers from 1 to 20, progressing in a clockwise direction. First, contestant 2 is eliminated. Then, the contestant two positions clockwise from where 2 was (i.e., contestant 4) is eliminated. Next, the contestant two positions clockwise from them (i.e., contestant 6) is eliminated. The counting continues in this manner, wrapping around the circle, which tightens after each elimination. So after contestant 20 is eliminated, the next contestant to go is 3, who at this point is two positions clockwise from where 20 once stood.
You repeat this process until only one contestant remains as the ultimate winner of the game. What is the winner’s number?
Extra Credit
For this week’s extra credit, you run the Squid Game competition again with the same 20 contestants, but now with slightly different rules.
Instead of always proceeding two positions clockwise for each elimination, you now proceed two or three positions clockwise. That is, for each turn, you randomly (and independently of the other turns) pick either two or three positions to move, each with a 50 percent probability. No longer is number 2 guaranteed to be the first contestant eliminated—now numbers 2 and 3 are equally likely to be eliminated first.
Once again, you proceed clockwise around the circle, tightening it after each contestant is eliminated, until only one contestant remains. This time around, which number is most likely to win the game?
Making the Rounds
There’s so much more puzzling goodness out there, I’d be remiss if I didn’t share some of it here. This week, I’m sad to announce that the math game Digits from The New York Times, which inspired last week’s Fiddler and is a favorite in my household, will apparently be “going away” on August 8th.
Reader David Gedye reached out to me to share some of his own writing about the computational complexity of Digits. In reviewing David’s analysis, one puzzle that jumped out at me was the following: If the six numbers you are presented with in Digits are simply the whole numbers from 1 to 6, what is the smallest positive integer you cannot generate? (Spoiler alert: David reveals the answer!)
Last Week’s Fiddler
Congratulations to the (randomly selected) winner from last week: 🎻 Billy Mullaney 🎻, from Minneapolis, Minnesota. I received 128 timely submissions, of which 43 were correct—for a rather pedestrian 34 percent solve rate. (Okay, this was trickier than I expected!)
Last week, you had to write an expression using the whole numbers 1, 2, 3, 4, and 5, and the operations of addition, subtraction, multiplication, and division. Importantly, you had to use each number and operation exactly once. Also, you could use as many parentheses as you wanted, but no concatenation of the digits was allowed (i.e., you couldn’t combine 2 and 3 to make the number 23). For example, one such number you could have generated was 7, since you could write that as (2÷1)×3+5−4.
What was the largest value you could generate in this way, using the five digits and four operations? (Note: Unlike Digits, fractional values were allowed.)
The key here was to get the most out of your addition and multiplication operations, which increased the overall value of the expression, while minimizing the impact of subtraction and division. You wanted to somehow combine the bigger numbers—3, 4, and 5—using addition and multiplication. The best way to do this was 5×(3+4), which gave you 35. From there, you had to figure out what to do with the remaining two digits and two operations.
While it wasn’t the right answer, 28 readers proceeded to subtract 1÷2. This gave them the expression 5×(3+4)−1÷2, which equaled 34.5. But as I just suggested, it was possible to do even better—provided you used another set of parentheses.
The optimal expression was 5×(3+4)÷(2−1). Rather than subtract a fraction, you could divide by 1 to keep the value right at 35.
Last Week’s Extra Credit
Congratulations to the (randomly selected) winner from last week: 🎻 Goh Pi Han 🎻, from Malaysia. For the Extra Credit, I received 64 timely submissions, 19 of which were correct—good for a respectable 30 percent solve rate.
For last week’s Extra Credit, instead of five numbers and four operations, you now had nine numbers (the whole numbers from 1 to 9) and eight operations (each of the four basic operations, twice). As before, you had unlimited parentheses, while concatenation was not allowed.
What was the largest value you could generate using these nine digits and eight operations?
While subtraction and division were your enemies in last week’s Fiddler, they served as valuable allies for the extra credit. Why? Because subtracting a negative quantity, as well as dividing by a fraction less than 1, increased the value of your expression. For example, dividing by (1÷9) was equivalent to multiplying by 9.
The optimal expression turned out to be
which equaled a whopping 9,900.
But the fun didn’t end there. For the bravest of souls, I asked for the largest numbers you could generate using the numbers from 1 to 4N+1 and N copies of each of the four operations. For N = 1, we already said the answer was 35. For N = 2, the answer was 9,900. But what about larger values of N?
For starters, getting some upper bounds on these values wasn’t too tough. For example, if you had been allowed to use each of the four operations as many times as you had wanted, you could have multiplied all the whole numbers together to get (4N+1)!. Actually, you could have done a little better by adding 2 and 1 and then multiplying by 3, rather than multiplying by both 2 and 1, giving you (3/2)×(4N+1)! However, finding the true maximal values was much tougher than finding an upper bound.
This week’s winner, Goh Pi Han, was able to generate some rather sizable expressions for N = 3 and 4. For N = 3, the expression
equaled to 4,392,300. And for N = 4, the expression
equaled to 1,269,859,200.
Solver Mike O'Connor did even better. For N = 3, the expression
equaled 4,478,760. And for N = 4, the expression
equaled 4,704,860,160. Wow!
Want to Submit a Puzzle Idea?
Then do it! Your puzzle could be the highlight of everyone’s weekend. If you have a puzzle idea, shoot me an email. I love it when ideas also come with solutions, but that’s not a requirement.
I will admit to being a little bit frustrated that my solutions for N > 2 were overlooked somehow. I will roughly rewrite what I submitted, and, of course, remove embarrassing errors and false paths that I submitted privately. I worked collaboratively with another user named SeerSkye, and much of this work was found by him while I was still messing around with slow computer code.
N=3 => 13 * 12 * (11 + 4) * (1/(10 + 5))/(6 + 9)/(8 - (2 - 3 - 7)) = 8,424,000
N=4 => 17 * 16 * 15 * (11 + 9) * (12 + 8)/((1/(13+7) /(14+6)/(10 - (2 - 5 - 4 - 3)) = 13,056,000,000
N=5 => 21 * 20 * 19 * 18 * (17 + 7) * (16 + 9) / ((1 / (15 + 10))/(14 + 11)/(13 + 12)/(8 - (2 - 6 - 5 - 4 - 3)) = 32,319,000,000,000
The general strategy is to recognize that all /s can become *s after the first one, and all -s can become +s after the first one. If we sacrifice the 1 to the /, and the 2 to the -, we can then try to even out all of the products as much as possible. In general, it seems like the best that we can do is:
product(3N+3..4N+1) * ceil(S/(N+1))^(S mod N+1) * floor(S/(N+1))^(N+1-S mod N+1)
where S = sum(3..3N+2) - 2
Which is an upper bound, actually satisfying this upper bound is probably impossible for all N.
However, we have a little bit of tug of war going on here, because the more digits we use in a single expression the worse the expression gets, and this assumes we use all of the minuses in a single term. If instead we allow ourselves to consider also sacrificing the 3, 4, 5, and so on for larger and larger N, we can begin to do better. The first N where this becomes absolutely desirable to do is N=21. So we have to create larger upper bounds.
N=21 (sacrifice 2 only) => 1858561114113223590154513972642442186649575491096420050912878442728057261260800000
N=21 (sacrifice both 2 and 3) => 1861170011681117541222317931520613643629245091916594782109445096734720000000000000
This more general expression is:
```
def poc(upper, lower):
return prod(range(lower, upper+1))
def sac(n, j):
s = sum(range(j+1, 3*n + j+1)) - sum(range(2, j+1))
return poc(4*n + 1, 3*n + j+1) * ceil(s/(n + j - 1))**(s % (n + j - 1)) * floor(s / (n + j - 1))**((n + j - 1) - (s % (n + j - 1)))
```
Where `sac(21, 2)` considers just the 2 case, `sac(21, 3)` also considers the 3 case. Our upper bound then is the maximum over j = 2..n of `sac(n, j)`
Unfortunately, actually finding explicit expressions for N=21 that correspond to this upper bound is not something I was able to do by hand, and I was unable to write a computer program to do so by the time submissions closed.
I guess it was too much to hope that someone had devised a general algorithm for finding the best combo of operations for any n