\n
Let\u2019s call $q$ the probability that a stormtrooper blasts us. In the problem, $q=\\tfrac{1}{1000}$. Let\u2019s 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\u2019t get blasted.<\/p>\n
\n
The probability that we blast a stormtrooper is given as $q K\\sqrt{N}$.\n<\/li>\n
The probability that one stormtrooper doesn\u2019t blast us is $1-q$ so the probability that we don\u2019t get blasted by any of the $N$ stormtroopers is $\\left(1-q\\right)^N$.\n<\/li>\n<\/ul>\n
Assembling these probabilities, we can write the following recursion:
\n\\begin{align}
\nP(0) &= 1 \\\\
\nP(N) &= \\left(1-q\\right)^N\\left[ \\left(1-q K\\sqrt{N}\\right)P(N) + q K\\sqrt{N}\\, P(N-1) \\right]
\n\\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\u2019s in a bit easier to work with:
\n\\[
\nP(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)
\n\\]Now it\u2019s 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
\n\\[
\nP(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)}
\n\\]<\/p>\n
Exact formula<\/h3>\n
There doesn\u2019t 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$.<\/p>\n
$\"\"$ <\/a><\/p>\n
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.<\/p>\n
Expanding the recursion as a function of $K$, the solution for $P(9)$ turns out to be the following rational function:
\n\\[
\nP(9) \\approx
\n\\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}
\n\\]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$:<\/p>\n
$\"\"$ <\/a><\/p>\n
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.<\/p>\n
Note:<\/strong> It\u2019s 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 \u201cblasting all the stormtroopers\u201d meant that we also survived the encounter!<\/p>\n
Approximate solution<\/h3>\nIn 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<\/a>. 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:
\n\\[
\nP(N) = \\prod_{n=1}^N \\frac{K}{K + \\sqrt{n}}
\n\\]Note that $q$ actually cancels! The formula above represents the limit as $q\\to 0$, which we\u2019re 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\u2019t appear to be a closed-form solution, but we can approximate further\u2026 Taking logs of both sides, we obtain:
\n\\[
\n-\\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)
\n\\]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:
\n\\[
\nK = \\frac{1}{\\log 2} \\sum_{n=1}^9 \\sqrt{n} \\approx 27.85
\n\\]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\u2019t better is because $x$ isn\u2019t actually that<\/em> 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:
\n\\[
\n-\\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)
\n\\]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$.<\/p>\n<\/div>\n
<\/p>\n<\/body>","protected":false},"excerpt":{"rendered":"
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 … Continue reading “Fighting stormtroopers”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":1700,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[8,15,2],"class_list":["post-1684","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-probability","tag-recursion","tag-riddler"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t