This week’s Riddler Express problem is a nod to the recently released finale to the Avengers saga. No spoilers!
Thanos, the all-powerful supervillain, can snap his fingers and destroy half of all the beings in the universe.
But what if there were 63 Thanoses, each snapping his fingers one after the other? Out of 7.5 billion people on Earth, how many can we expect would survive?
If there were N Thanoses, what would the survival fraction be?
Here is my solution:
[Show Solution]
First things first: If there are $S$ Thanos snaps and the probability of survival after one snap is $p$, then the expected fraction of survivors is $p^S$. In the case where the population is $7.5$ billion and the probability of survival is $p=0.5$, if there are $S=63$ snaps, we can calculate the expected number of survivors to be:
\[
\frac{7.5\times 10^9}{2^{63}} = 8.13\times 10^{-10}
\]This number is so small that there will almost certainly be no survivors.
A more interesting interpretation: But what if Thanos were not immune to the snap? After all, when Thanos snaps his fingers, half of all the beings in the universe are destroyed! This should include Thanos! So when the first Thanos snaps his fingers, on average half of the remaining Thanoses will be destroyed before having the opportunity to snap their fingers.
This means that $S$, the total number of snaps, is a random variable. We can compute its probability mass function recursively. Specifically, let’s define $P_N(s)$ to be the probability that there will be $S=s$ snaps given that there are initially $N$ Thanoses. Let’s start with some easy cases.
- If there are no Thanoses, there will be no snaps. So $P_0(0) = 1$.
- If there is at least one Thanos, there will be at least one snap. So $P_N(0) = 0$ for $N=1,2,\dots$.
The recursion for larger values of $s$ is given by:
\begin{align}
P_N(s) &= \sum_{k=0}^{N-1} \mathrm{Prob}(k\text{ Thanoses survive first snap}) P_k(s-1) \\
&= \sum_{k=0}^{N-1} \binom{N-1}{k} p^{k}(1-p)^{N-1-k} P_{k}(s-1)
\end{align}This follows because if there are $s$ snaps remaining, then during the first one, the remaining $N-1$ Thanoses are at risk of destruction. The number of surviving Thanoses follows a binomial distribution with $N-1$ trials and probability $p$, which explains why the probability that $k$ survive the first snap is equal to $\binom{N-1}{k} p^{k}(1-p)^{N-1-k}$. This recursion can be evaluated numerically. Here is what the distribution of snaps looks like for $p=0.5$ and $N=63$:
So there will most likely be $5$ or $6$ snaps. Once we know how many snaps there are, the effect on the population of the universe is the same as in the first interpretation. So the expected fraction of survivors in the universe will be $\mathbb{E}(p^S)$, or:
\[
\mathbb{E}(\text{fraction of survivors if we have }N\text{ Thanoses}) = \sum_{s=0}^N p^s P_{N}(s)
\]Here is a plot of the surviving fraction as a function of $N$ when $p=0.5$:
When there are 63 Thanoses, the expected survival rate is about 2.22%. So with an initial population of 7.5 billion, we will be left with, on average, about 166.5 million.
If you’re curious about the shape of this graph, we can approximate it like this: With $N$ Thanoses and $p=0.5$, there are roughly $\log_2(N+1)$ flips that occur. If exactly that many flips occur, the fraction of survivors will be roughly $(0.5)^{\log_2(N+1)} = \tfrac{1}{N+1}$. This tells us that as $N$ gets large, the fraction of survivors will scale roughly like $\frac{1}{N}$, where $N$ is the number of Thanoses. This is a crude approximation, but it captures the correct asymptotic behavior.
If you’re interested in the (Python) code I wrote to generate this solution (and the figures), you can find it on github here.
Laurent,
Interesting interpretation! I simply assumed half of all people, and half all Thanoses (and half of those who had not yet snapped) were eliminated directly. For details, see https://colab.research.google.com/drive/1BaP6Buz6tLKRCm5lT3uvkw0A7OaBuSOO
Other interpretations are possible. For example, What if exactly half of Thanoses are eliminated with each snap, but each one’s chances of being eliminated is uniform among those Thanoses remaining? What if exactly half of all beings were eliminated with each snap, and the remaining Thanoses were lumped in with all of humanity for that uniform choice?
Laurent,
As Michael points out, there’s no reason why Thanos should be treated any differently from any other being (just more powerful at the present time). If the number of remaining Thanoses is even, then EXACTLY half of those Thanoses will be destroyed by a Thanos snap, not “on average.” This gives the answer of 6 snaps (and 1/64 of humanity left) for 63 Thanoses.
Michael,
We need the answer when N is not exactly 2^k-1. For L=floor(log(N,2)), the number of snaps will be either L or L+1, depending on how many Thanoses die at each snap when there are an odd number waiting to snap. My answer claimed that the expected number of snaps E(S) is a linear ratio between L and L+1, depending on how close N is to the respective power of 2 (e.g., for 6 Thanoses, there will be 3 snaps 75% of the time and 2 snaps 25% of the time). The expected fraction of humanity alive E(p) is then 1/2^E(S), and the full solution would be:
E(p) = (3 x 2^L – N – 1) / (2^(2L+1))
I think you have to be careful when saying that “exactly half of Thanoses must be destroyed”. This was never explicitly stated in the question! You said Thanoses shouldn’t be treated differently, but that’s precisely what you’re doing! Your implicit assumption here is that Thanoses are part of a group of entities, and so are the humans living on earth, and exactly half of the entities in each group must be destroyed.
If this interpretation is going to make sense, there needs to be an unambiguous way of determining which group an entity belongs to. If it’s possible for an entity to belong to more than one group, then we’ll have a contradiction. Here is a counterexample: Let’s say Group A is {Alex,Bob}, Group B is {Bob,Charlie}, and Group C is and {Alex,Charlie}. There is no way to eliminate exactly one person from each of the three groups. So this rules out using any groups we like, such as “teenagers”, “people over six feet tall”, “people with black hair”, and so on… because then people will belong to more than one group and we’ll have problems.
So we must have an unambiguous way of subdividing entities into groups. Perhaps by their DNA? I guess we’ll look at different species and put them in different groups? But what defines a species? Does this mean that ligers (yes they do exist!) should be considered tigers or lions? Should ligers be their own group? Or should tigers and lions be the same group since evidently they can breed together? There is no obvious way to do this… Inevitably, you’ll be left with two entities with different DNA, and you’ll be forced to decide, based on how different their DNA is, whether they belong to the same group or not. This is a problem if A and B are close enough to be considered the same group, and so are B and C, but A and C are too different. Then B will belong to both A’s group and C’s group, a contradiction. If you really want to use DNA, the only unambiguous way to do so is to make a group for each unique DNA strand. But this places each individual in their own group, and we have reduced the problem to just flipping a coin for each entity to see if they get destroyed or not (which is the version of the problem I solved).
As Michael pointed out, there are many possible interpretations. Without specific instructions, there is no way to know exactly how to proceed. I chose my interpretation precisely because it seemed the most fair; every entity has a 50% chance of survival, regardless of which group they belong to. This also seems the most in-line with Thanos’s words in the Avengers movies, for what it’s worth…
Hi Laurent,
If we assume that:
– being the wielder of the gauntlet confers protection from the act of snapping the thanos that snaps survives his own snap.
– All other thanos (n-1) are 50% chance of being eliminated
– each thanos only has a desire to halve the population once – a desire that is satisfied after a single snap
So after each snap there is a new benign Thanos, that has a 50% chance of surviving a future snap…
This increases the probability that each snap is the last snap in the sequence (as the probability of number of benign thanos = the total number of remaining thanos increases with each snap)
Any idea how it would work out if the scenario played out according to these assumptions above?
I’m not sure what you mean by “benign Thanos”. Do you mean a Thanos that will not snap when their turn rolls around? There are two random processes happening here. The first is the process that determines how many snaps will happen. The second is the process that determines how many people survive this number of snaps. I think what you’re suggesting (that each time a snap occurs, some of the Thanoses that haven’t snapped yet will drop out of contention and will not snap when their turn comes up), will only affect the first process. So yes, what you suggest will tend to reduce the number of snaps that occur and therefore increase the number of survivors.