This Riddler puzzle is about fighting a group of stormtroopers. Why *are* they so inaccurate anyway?

In Star Wars battles, sometimes a severely outnumbered force emerges victorious through superior skill. You panic when you see a group of nine stormtroopers coming at you from very far away in the distance. Fortunately, they are notoriously inaccurate with their blaster fire, with only a 0.1 percent chance of hitting you with each of their shots. You and each stormtrooper fire blasters at the same rate, but you are $K$ times as likely to hit your target with each shot. Furthermore, the stormtroopers walk in a tight formation, and can therefore create a larger target area. Specifically, if there are $N$ stormtroopers left, your chance of hitting one of them is $(K\sqrt{N})/1000$. Each shot has an independent probability of hitting and immediately taking out its target. For approximately what value of $K$ is this a fair match between you and the stormtroopers (where you have 50 percent chance of blasting all of them)?

Here is my solution.

[Show Solution]

Let’s call $q$ the probability that a stormtrooper blasts us. In the problem, $q=\tfrac{1}{1000}$. Let’s call $P(N)$ the probability that we will blast all of the $N$ stormtroopers and survive to tell the tale. Each round, several things can happen. We can blast a stormtrooper (or not) and we can get blasted ourselves (or not). One thing for sure is that we can only advance if we don’t get blasted.

- The probability that we blast a stormtrooper is given as $q K\sqrt{N}$.
- The probability that one stormtrooper doesn’t blast us is $1-q$ so the probability that we don’t get blasted by any of the $N$ stormtroopers is $\left(1-q\right)^N$.

Assembling these probabilities, we can write the following recursion:

\begin{align}

P(0) &= 1 \\

P(N) &= \left(1-q\right)^N\left[ \left(1-q K\sqrt{N}\right)P(N) + q K\sqrt{N}\, P(N-1) \right]

\end{align}The initial condition is that when there are no stormtroopers left, we have a 100% chance of blasting them all so $P(0)=1$. This recursion can be rearranged so that it’s in a bit easier to work with:

\[

P(N) = \left( \frac{\left(1-q\right)^N\left(q K\sqrt{N}\right)}{1-\left(1-q\right)^N\left(1-q K\sqrt{N}\right)}\right) \, P(N-1)

\]Now it’s clear that we can substitute $P(0)$ and solve for $P(1)$, and then solve for $P(2)$, and so on. So the probability is given by the formula

\[

P(N) = \prod_{n=1}^N \frac{\left(1-q\right)^n q K\sqrt{n}}{1-\left(1-q\right)^n\left(1-q K\sqrt{n}\right)}

\]

### Exact formula

There doesn’t appear to be any way to simplify the product above, so we resort to a numerical solution. Here is a plot that shows the probability of blasting all the stormtroopers as a function of the number of stormtroopers $N$ and the blasting efficiency ratio $K$.

The plot above makes sense; our chances of blasting all the stormtroopers increases as $K$ increases (we get better at shooting them) or as $N$ decreases (there are fewer stormtroopers). We can also estimate that to blast 9 stormtroopers 50% of the time (without getting blasted ourselves!) we should have $K\approx 25$. In order to get a more precise estimate of $K$, we must do a bit more work.

Expanding the recursion as a function of $K$, the solution for $P(9)$ turns out to be the following rational function:

\[

P(9) \approx

\tfrac{K^9}{K^9+19.37 K^8+165 K^7+810 K^6+2524 K^5+5176 K^4+6972 K^3+5943 K^2+2904 K+619}

\]The only approximation I used here was in rounding the coefficients in the denominator. This function starts at zero when $K=0$ and increases monotonically and asymptotically to 1 as $K\to\infty$. This makes sense; the better we shoot, the likelier we are to blast all the stormtroopers! Here is a plot of $P(9)$ as a function of $K$:

Solving $P(9)=0.5$ numerically for $K$, we obtain $K\approx 26.797$. So in order to have a 50% chance of surviving an encounter with 9 stormtroopers, we should be roughly 27 times more accurate.

**Note:** It’s also possible that we blast all the stormtroopers but on our last shot, we also get blasted. I did not account for this possibility because I assumed that “blasting all the stormtroopers” meant that we also survived the encounter!

### Approximate solution

In this scenario, $q$ is very close to zero and $N$ is small as well. So we can approximate $q^2 \approx 0$. This is effectively a first order Taylor expansion. This allows us to write $(1-q)^n \approx 1-nq$, for example. By applying $q^2 \approx 0$ in the original formula, we obtain the simpler product:

\[

P(N) = \prod_{n=1}^N \frac{K}{K + \sqrt{n}}

\]Note that $q$ actually cancels! The formula above represents the limit as $q\to 0$, which we’re assuming is a good enough approximation given that $q = \tfrac{1}{1000}$ is so small. Solving it numerically, we obtain $K \approx 26.707$, which is pretty close to the true solution of $K=26.797$. Unfortunately, this is still a problematic expression and there doesn’t appear to be a closed-form solution, but we can approximate further… Taking logs of both sides, we obtain:

\[

-\log P(N) = \sum_{n=1}^N \log\left( 1 + \tfrac{\sqrt{n}}{K} \right) \approx \frac{1}{K}\left(\sum_{n=1}^N \sqrt{n}\right)

\]The approximation we made stems from the fact that the expression on the right is of the form $\log(1+x)$ and $x$ is relatively small (we expect $K\approx 25$ and $n < 10$, therefore $x = \tfrac{\sqrt{n}}{K} < 0.12$). The approximation we used is a first order Taylor approximation $\log(1+x) \approx x$. If we want to find the $K$ such that $P(9) = 0.5$, we can solve this easily and obtain:
\[
K = \frac{1}{\log 2} \sum_{n=1}^9 \sqrt{n} \approx 27.85
\]This is reasonably close to the $K\approx 26.707$ we were looking for and a lot easier to work with! The reason our approximation isn't better is because $x$ isn't actually *that* close to zero. To get a better approximation, we can use the second order Taylor approximation $\log(1+x)\approx x-\tfrac{1}{2}x^2$ and we obtain the equation:

\[

-\log P(N) \approx \frac{1}{K} \left( \sum_{n=1}^N \sqrt{n} \right)-\frac{1}{2K^2} \left( \sum_{n=1}^N n \right)

\]This is a simple quadratic equation in $K$ and solving it with $N=9$ and $P(9)=0.5$ yields the solution $K\approx 26.63$, which is much closer to the $K\approx 26.707$ we were approximating and still pretty close to the true solution $K=26.797$.

Maybe slightly simpler (but still numerical): Facing N stormtroopers, your chance of killing a stormtrooper before they kill you is (p-pq)/(p + q – pq), where p is your chance of killing with each shot, that is, (K*sqrt(N))/1000, and q is their chance of killing you with one shot each, which is one minus the chance of their all missing, or (1 – (.999)^N). Your chance of survival is the product of the chances of your killing first for N from 9 to 1.

I just knocked out a straight simulation, which is easily good enough for a couple of significant digits: https://gist.github.com/rvcx/808d1b669eaa326d9fa2b7cebcf8c359

Here’s my Mathematica code to solve for K as a function of N, https://gist.github.com/ShiangYong/f85a481510fdb860da3d13f54b044c0e

Here are the values I got for 9<=N<=20

N=9 – 26.7969

N=10 – 31.3241

N=11 – 36.0804

N=12 – 41.0557

N=13 – 46.2411

N=14 – 51.6288

N=15 – 57.2119

N=16 – 62.9841

N=17 – 68.9399

N=18 – 75.0741

N=19 – 81.3819

N=20 – 87.8591