9
$\begingroup$

A gun shots bullets with different speed each second.
The bullets form a straight line.
The bullets keep their speed (not getting slower or faster).
But if 2 of the bullets collide, 2 of them are destroyed (annihilated)
The gun stops after 12 bullets fired.

What is the probability that all the bullets will be destroyed ?

There is a beautiful math formula for every even bullets fired, find it!

This is a puzzle from a good website, I will show the link after the puzzle solved.

$\endgroup$
  • $\begingroup$ Doesn't it depend on the probability distribution of the speed of the bullets? $\endgroup$ – Wen1now Dec 11 '17 at 5:23
  • $\begingroup$ @Wen1now : It's part of the puzzle. $\endgroup$ – Jamal Senjaya Dec 11 '17 at 5:25
  • 3
    $\begingroup$ math.stackexchange.com/questions/1526292/colliding-bullets $\endgroup$ – votbear Dec 11 '17 at 7:01
  • 1
    $\begingroup$ I think it will turn out that the only thing that matters is which bullets are faster than which other bullets, in which case the distribution is irrelevant. $\endgroup$ – Gareth McCaughan Dec 11 '17 at 11:00
  • 1
    $\begingroup$ The speed distribution is important. For four bullets, numbered 1-4, with 1 fastest and 4 slowest, if they are fired in the order 2-4-3-1, then 1 would catch 3, but only if 3 doesn't catch 4 first. If 3 catches 4 first, then they disappear and 1 hits 2, all destroyed. But if 1 hits 3 first, then 4 will never catch 2 and two survive. $\endgroup$ – user3294068 Dec 11 '17 at 17:07
3
$\begingroup$

I am adding another answer since my first try was way off the mark.

Solution

Key thing to notice is that, for 12 bullets to be eliminated, there has to be 6 collisions in total involving any bullets in any order.

That means we don't have to workout all possible relative speeds and their respective probability of total elimination. We just need to calculate the probability of 6 succesive collisions to happen.

If the first bullet is the fastest, it will escape and the probability of this happening is 1/12. But if first bullet is not the fastest, there is guaranteed to be at least one collision (it doesn't matter that the first bullet may escape this collision, we will account for it in later collisions).

So the probability of at least one collision happening when 12 bullets are involved is:

$$p_{12} = 1 - \frac{1}{12}$$

For the second collision, we only have 10 bullets left. Following the same logic, if the first among the surviving bullets is not the fastest, there is chance for at least one more collision happening. So the independent probability of second collision is $p_{10} = 1 - \frac{1}{10}$.

In general, so for a scenario with n bullets, the independent probability of at least one collision happening is:

$$p_{n} = 1 - \frac{1}{n}$$

Looking back at our key insight, the probability of total annihilation is same as that of 6 successive collision events to happen, which is:

\begin{align} p &= p_{12}*p_{10}*p_8*p_6*p_4*p_2 \\\\ &= (1 - \frac{1}{12})*(1 - \frac{1}{10})*(1 - \frac{1}{8})*(1 - \frac{1}{6})*(1 - \frac{1}{4})*(1 - \frac{1}{2}) \\\\ &= 0.2256 \end{align}

General solution

General formula for n bullets would be: \begin{align} p &= (1 - \frac{1}{n})*(1 - \frac{1}{n-2})...(1 - \frac{1}{4})*(1 - \frac{1}{2}) \end{align}

$\endgroup$
  • 1
    $\begingroup$ This does assume that the distribution of speeds in the bullet swarm remains independent of bullet position after a collision has occurred. In other words, I agree that the chance the first bullet will escape due to being fastest of 12 is 1/12. But if a collision has occured, and there are 10 bullets remaining, and the first bullet was not one of the colliding pair, then is it still valid to assume that it is equally likely (1/10) to be the fastest of the remaining bullets? (My quick simulation suggests otherwise). $\endgroup$ – Penguino Dec 18 '17 at 2:27
  • $\begingroup$ Yes, I think the probability of a bullet being the fastest is still 1/n where n is the number of bullets, irrespective of whether the bullets have survived collision or not. It is because probabilities after each collision is independent of what happened before. I am not a statistician, so I may be missing something here. It will be great if you can explain your simulation in detail. $\endgroup$ – Benny Dec 18 '17 at 16:07
1
$\begingroup$

Let us try to solve this by solving smaller problems and gradually adding more complexity to it.

Probability of two bullets colliding

First we estimate the probability of two consecutive bullets colliding. We can plot the relative time-distance graph for first bullet as a 45 degree line. Since both time and distance are infinite, we can adjust the scale to make it 1:1.

Now the second bullet won't hit the first bullet as long as its speed is lower than that of first, that is the bottom half of our plot. The probability can be arrived by dividing the area under the line with the total area of the chart

$p = 0.5$

Relative speed

Probability of first bullet not colliding even after 11 succesive shots

This is the probability of drawing 11 lines of any angle (speed) as long as they are less than 45 degrees. Since speed of each shot is purely random and independent of prior shot, the actual probability is a conditional probability of the non-event happening 11 times (the number of possible encounters with the following bullets) in succession.

$p = (0.5)^{11}$

Probability of first bullet getting destroyed

This is simple. It is merely the inverse probability of previous event. Since this event is directly related to the answer we want, let us index this as p1.

$p1 = 1 - (0.5)^{11}$

Probability of nth bullet getting destroyed

For 2nd bullet (the cardinal position is relative, number 2 referring to the next non-destroyed bullet), it has 9 possible encounters (a pair lost to prior collision). So $p2 = (0.5)^9$. Similarly probabilities for remaining bullets can be calculated as:

$p2 = 1 - (0.5)^9$
$p3 = 1 - (0.5)^7$
$p4 = 1 - (0.5)^5$
$p5 = 1 - (0.5)^3$
$p6 = 1 - (0.5)^1$

Probability of all the bullets getting destroyed

Now I consider this as the probability of above 6 events happening successively.

$p = p1 \times p2 \times p3 \times p4 \times p5 \times p6$
$p = (1−(0.5^{11}))\times(1−(0.5^9))\times(1−(0.5^7))\times(1−(0.5^5))\times(1−(0.5^3))\times(1−(0.5^1))$
$p = 0.4195$

So there is a 42% chance that all bullets will be lost.

disclaimer

There may be some holes in my logic, particularly with respect to chaining events $p1$-$p6$. I considered the 6 possible collisions as independent events, I am not sure whether my assumption is valid.

$\endgroup$
  • $\begingroup$ I don't know if I agree with your P(first bullet doesn't get destroyed). It doesn't have to be faster than the rest of them, just some of them. In a smaller example, with four bullets A, B, C, and D, if A is faster than B and D, it can be slower than C and not be destroyed. $\endgroup$ – DqwertyC Dec 11 '17 at 17:18
  • $\begingroup$ //In a smaller example, with four bullets A, B, C, and D, if A is faster than B and D, it can be slower than C and not be destroyed.// Eventually C will catch up to A and destroy it since we are dealing with infinite time here, right? Or you are referring to the case where C will catch up to either B or D and get destroyed first? $\endgroup$ – Benny Dec 11 '17 at 17:28
  • $\begingroup$ C will catch up with B, and both B and C will be destroyed. Then, D would never catch up with A. $\endgroup$ – DqwertyC Dec 11 '17 at 17:35
  • $\begingroup$ To clarify, A is shot first, then B, then C, then D. $\endgroup$ – DqwertyC Dec 11 '17 at 17:37
  • $\begingroup$ @Benny : 42% is too big. $\endgroup$ – Jamal Senjaya Dec 12 '17 at 8:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.