The Squid Game Riddle
Probability: Easy
Probability Puzzle
This was featured last week on FiveThirtyEight’s Riddler Classic: apparently inspired by Netflix’s breakout hit The Squid Game. I am yet to see that show: undecided on starting it, but that it might feature elements of the puzzle below, might just tip the scales in favor of a binge watch. This is a relatively easy one:
Prereqs: Basic Probability and Permutation/Combinations
The puzzle reproduced in entirety from the Riddler Page:
Congratulations, you’ve made it to the fifth round of The Squiddler — a competition that takes place on a remote island. In this round, you are one of the 16 remaining competitors who must cross a bridge made up of 18 pairs of separated glass squares. Here is what the bridge looks like from above:
To cross the bridge, you must jump from one pair of squares to the next. However, you must choose one of the two squares in a pair to land on. Within each pair, one square is made of tempered glass, while the other is made of normal glass. If you jump onto tempered glass, all is well, and you can continue on to the next pair of squares. But if you jump onto normal glass, it will break, and you will be eliminated from the competition.
You and your competitors have no knowledge of which square within each pair is made of tempered glass. The only way to figure it out is to take a leap of faith and jump onto a square. Once a pair is revealed — either when someone lands on a tempered square or a normal square — all remaining competitors take notice and will choose the tempered glass when they arrive at that pair.
On average, how many of the 16 competitors will survive and make it to the next round of the competition?
Solution:
Hint: This question becomes relatively straightforward once you realize
- the connection between contestant outcomes and fair coin tosses
- the average survivor count is just a weighted average of all the possible survivor outcomes (0 – 16) with the weights being the probability of each outcome
Method 1
A contestant stepping on a square is essentially facing a coin toss with 50-50 odds (A Bernoulli trial with p = 0.5 ). What we then have is potentially up to 18 coin tosses with tails (or heads if you please) representing a broken glass square sending the contestant to a bottomless pit.
For n contestants to survive you need to have exactly 16 – n of the 18 coin tosses result in the tails outcome. The number of ways in which you can achieve 16-n tails is the no. of ways you can select 16-n slots from 18, which is (ref Combinations).
\displaystyle\binom{18}{16-n} \\The total number of possible outcomes (heads tails combinations) for 18 coin flips given each can have only one of two outcomes (heads or tails) is 2^{18}. So the probability of there being n survivors ( n between 1 and 16) is
\displaystyle\binom{18}{16-n}/2^{18}\\This can be calculated for each n from 1 survivor to 16 survivors. We don’t need the n = 0 case since it will contribute exactly 0 to the final weight.
So the final answer is the weighted sum:
\displaystyle\sum\limits_{n=1}^{16}n\displaystyle\binom{18}{16-n}/2^{18} \ \ = \ \ \large 7.00007629394531\\This as you can tell is really close to the number 7 which is intuitively what you get if you assume that you lose half a person at each square pair (16-0.5\cdot 18 = 7). So why is the answer not 7, but a wee bit higher? Let’s look at a different solution to understand this.
Method 2: following the intuition that we lose half a contestant on average at each step
We have a success/failure probability at each square of 0.5. So on average we lose half a contestant at each square pair provided there is a contestant available at that step. This last underlined part is really important for our current line of reasoning. We’ll come back to it in a bit. So, for now, it’s reasonable to expect that with 18 steps we will lose 9 contestants on average and so the answer must be 16 – 9 = 7 survivors on average. But if you followed method 1 above, you’ll note that the answer is actually slightly greater than 7. So what’s the flaw in this reasoning?
It’s that underlined bit above! With fewer contestants than square glass pairs, we cannot guarantee there is someone to step on a square at steps 17 and 18. Why? Because there is a non-zero probability that we lose all 16 in the first 16 or 17 steps! So the probability of losing a contestant on square 17 or 18 is going to be less than 0.5. Let’s calculate this:
Squares 1 – 16: we lose 0.5 contestant per square pair. So 8 lost on average.
Square 17: We lose 0.5 person provided there is at least one survivor in squares 1 – 16; 0 people otherwise. Can’t lose anyone if there is no one left to step on it!
So the average lost on Step 17 = 0.5 X probability of at least survivor in steps 1 through 16.
= 0.5\ \cdot\ Prob(15\ or\ fewer\ tails\ in\ first\ 16\ coin\ flips) \\ = 0.5\ \cdot\ (1\ -\ Prob(exactly\ 16\ tails\ in\ 16\ coin\ flips))\\ = 0.5\ \cdot\ (1\ -\ 0.5^{16})\\ = 0.4999923706Square 18: Similar to square 17:
= 0.5 \cdot Prob(15\ or\ fewer\ tails\ in\ first\ 17\ coin\ flips) \\ = 0.5\ \cdot\ (1\ -\ Prob(16\ or\ 17\ tails\ in\ 17\ coin\ flips))\\ = 0.5\ \cdot\ (1\ -\ \binom{17}{16}0.5^{17}\ -\binom{17}{17}0.5^{17} )\\ = 0.4999313354 \\Adding them all up we get: 8.999923706 lost contestants on average or
16\ – 8.999923706\ = \large 7.00007629394531 surviving contestants on average, same as before!
Closing it out
It should be obvious then that the solution when the no. of contestants k equals or exceeds the no. of square-step pairs n , the average number that are eliminated are \displaystyle \frac{n}{2} and the average survivors are consequently \displaystyle k – \frac{n}{2} .
It’s not too hard to show that for the general case of n square step pairs, j fewer contestants than square pairs and hence k = n-j\ contestants, the expected (average) number of survivors is:
\displaystyle\frac{n}{2}\ -\ j\ +\ \sum\limits_{i=1}^{j} i \binom{n}{n-j+i} (0.5)^{n} \\If you have an alternative and esp. easier solution, please describe it in the comments.
2 thoughts on “The Squid Game Riddle”
Lucid explanations! Thanks Arvind!!
Thanks Shankar 🙏🏽