Random bullets

[bonanova]

Here is a simple puzzle using bullets fired at random speeds along a straight line.

1. Every second, a gun shoots a bullet along a straight line.
2. Each bullet has a random speed between 0 and 1.
3. Bullets do not slow down; but if two bullets collide, both of them are annihilated.
4. The gun stops shooting after 10 bullets have been fired.

What is the probability that eventually all the bullets will be annihilated?

Edit:

BMAD previously asked if the bullets never stop firing, whether (at least) one bullet survive forever.
It inspired a lot of debate, I think without resolution.
This puzzle I think has a provable answer.

For starters, solve the problem using 4 bullets.

Edited October 28, 2015 by bonanova
Give credit to BMAD's earlier puzzle

[dgreening]

I seem to recall, something similar to this.

I assume we can use the following simplifying assumptions:

• Bullets travel to infinity [unless annihilated]
• Bullets follow the same path [or can be assumed to follow a straight line]

As I recall, it doesn't take many bullets before the leaders continue on undamaged.

Obviously if the first bullet is the fastest of the 10, then they will not all annihilate [10%]

similarly if the last bullet is the slowest of the 10, then they will not all annihilate  [10%]

There are many variations of these conditions that lead to at least 1 [actually 2] bullets continuing on.

So the probability is certainly less than 80% and I suspect it is closer to 20% ..

 

 

[bonanova]

I seem to recall, something similar to this.

I assume we can use the following simplifying assumptions:

• Bullets travel to infinity [unless annihilated]
• Bullets follow the same path [or can be assumed to follow a straight line]

Hidden Content

Hidden Content

 

You are correct that there was a similar previous problem. There, the gun was never turned off, and the question was the probability of at least one bullet not being annihilated. That thread had a lot of interesting discussion and simulations. Reading it now would not be considered cheating since for this problem a closed form is asked for. I tried searching once, without success, but I'm sure it's there.

Your observations are correct so far.

I am going to make the 4-bullet case part of the puzzle. I think it's simple enough to think through while having enough complexity to guide an analysis for the 10-bullet solution. So there are two questions now: What are pzilch(4) and pzilch(10)? Where pzilch(n) is the total-annihilation probability for n bullets.

Edited October 28, 2015 by bonanova
Added link to BMAD's earlier bullet puzzle

[dburns]

9/24 and 81/3628800

Edited August 21, 2015 by dburns

[bonanova]

Hidden Content

Hi dburns, and welcome to the Den.

First answer (3/8) is spot on, but the second on is a little low. Were you able to find a formula?

[plainglazed]

Spoiler for a stab at ten bullets

 

1/9?   ~.1127

Edited August 24, 2015 by plainglazed

[BMAD]

I am flattered  as this is very similar to one of my old questions. Except, mine shot for a duration as opposed to a finite number of times.

[bonanova]

Spoiler for a stab at ten bullets

 

Hidden Content

A little low.

[bonanova]

I am flattered  as this is very similar to one of my old questions. Except, mine shot for a duration as opposed to a finite number of times.

Yes, this one has a definitive answer. I'm not sure consensus was reached on the infinite puzzle.

[bubbled]

This is what I get with about 1M simulations.

 

All bullets are annihilated approximately 24% of the time

[bonanova]

This is what I get with about 1M simulations.

 

Hidden Content

That's a good result. Curious, what language did you do your simulation in?

[jasen]

Simulation by VBA :

Sub RandomBulletTest()
Dim Anhilated As Integer
Dim Bullets As Variant
Dim AllAnhilated As Single
Bullets = Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
    
    For Cnt = 1 To 500000
        ''random inisial speed between 0 to 1
        For i = 0 To 9
            Bullets(i) = Rnd
        Next i
        
        ' i for front bullet and j for bullet behind i
        ' if speed j > speed i then both bullets anhilated
        ' i assign -2 for anhilated bullets
        For i = 0 To 9
            For j = i + 1 To 9
                If Bullets(i) >= 0 Then
                    If Bullets(j) >= 0 And Bullets(j) > Bullets(i) Then
                        Bullets(j) = -2
                        Bullets(i) = -2
                        j = 10
                    End If
                End If
            Next j
        Next i
        
        'check how many bullet anhilated
        For i = 0 To 9
            If Bullets(i) < 0 Then
                Anhilated = Anhilated + 1
            End If
        Next i
        
        'test wheather all bullet anhilated or not
        If Anhilated = 10 Then
            AllAnhilated = AllAnhilated + 1
        End If
        Anhilated = 0
    Next Cnt
    Selection.TypeText Text:="      P of all anhilated = " + str(AllAnhilated / 5000000)
End Sub

---------------------------------

P of all anhilated =  .0349778     
P of all anhilated =  .0349992      
P of all anhilated =  .0350404

 

[bubbled]

This is what I get with about 1M simulations.

 

Hidden Content

That's a good result. Curious, what language did you do your simulation in?

It's in Python. My friend ( a much more professional programmer than me) wrote it, so I'd be uncomfortable commenting it. But here's the code:

 

 

import random

bullets = list()
bullets_fired = 0
seconds = 0

def simulate_second():
    global bullets
    if bullets_fired < 10:
        fire_bullet()       
    find_impacts_in_second()
    for bullet in range(0,len(bullets)):
        bullets[bullet][0] = bullets[bullet][0] + bullets[bullet][1]
        
def fire_bullet():
    global bullets_fired, bullets
    bullets_fired = bullets_fired + 1
    bullets.insert(0, [0.0, round(random.random(),2)] )
    

def find_impact_time( bx1, bv1, bx2, bv2 ):
    try:
        t = ( bx1 - bx2 ) / ( bv2 - bv1 )
    except ZeroDivisionError:
        return None
    if t < 0:
        return None
    return t

def find_impacts_in_second():
    global bullets
    if len(bullets) < 2:
        return None
    lowest_time = None
    lowest_bullet = None
    for front_bullet in range(len(bullets)-1, 0, -1):
        impact_time = find_impact_time( bullets[front_bullet - 1][0], bullets[
                front_bullet - 1][1], bullets[front_bullet][0], bullets[front_bullet][1] )
        if impact_time is not None and impact_time <= 1.0:
            if lowest_time is None or lowest_time > impact_time:
                lowest_time = impact_time
                lowest_bullet = front_bullet
    
    if lowest_bullet is not None:
        #print "removing index", lowest_bullet
        del bullets[lowest_bullet]
        del bullets[lowest_bullet-1]
        print bullets
        find_impacts_in_second( )
    else:
        return None

def will_ever_impact():
    global bullets
    for front_bullet in range( len(bullets) - 1, 0, -1):
        impact_time = find_impact_time( bullets[front_bullet - 1][0], bullets[
                front_bullet - 1][1], bullets[front_bullet][0], bullets[front_bullet][1] )
        if impact_time is not None:
            return True
bullet_survives = 0
for j in range(1000000):
    for i in range(0,10):
        simulate_second()
    
    while will_ever_impact():
        simulate_second()
    if bullets:
        bullet_survives += 1
    bullets = list()
    bullets_fired = 0

print "Final Tally"
print "Bullet Survives ", bullet_survives
print "No Bullets ", 1000000 - bullet_survives
print "P of survival ", float(bullet_survives) / 1000000.
print "P of total annihilation ", (1000000 - bullet_survives) / 1000000.

[bubbled]

Simulation by VBA :

Sub RandomBulletTest()
Dim Anhilated As Integer
Dim Bullets As Variant
Dim AllAnhilated As Single
Bullets = Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
    
    For Cnt = 1 To 500000
        ''random inisial speed between 0 to 1
        For i = 0 To 9
            Bullets(i) = Rnd
        Next i
        
        ' i for front bullet and j for bullet behind i
        ' if speed j > speed i then both bullets anhilated
        ' i assign -2 for anhilated bullets
        For i = 0 To 9
            For j = i + 1 To 9
                If Bullets(i) >= 0 Then
                    If Bullets(j) >= 0 And Bullets(j) > Bullets(i) Then
                        Bullets(j) = -2
                        Bullets(i) = -2
                        j = 10
                    End If
                End If
            Next j
        Next i
        
        'check how many bullet anhilated
        For i = 0 To 9
            If Bullets(i) < 0 Then
                Anhilated = Anhilated + 1
            End If
        Next i
        
        'test wheather all bullet anhilated or not
        If Anhilated = 10 Then
            AllAnhilated = AllAnhilated + 1
        End If
        Anhilated = 0
    Next Cnt
    Selection.TypeText Text:="      P of all anhilated = " + str(AllAnhilated / 5000000)
End Sub

---------------------------------

P of all anhilated =  .0349778     
P of all anhilated =  .0349992      
P of all anhilated =  .0350404

 

This code must be flawed. The absolute floor for annihilation is 10%. If the first bullet out of the gun is the fastest of the 10, then it must survive. That happens exactly 10% of the time. So, even if the interactions with the other bullets never helps, you know that at least 1 bullet must survive a minimum of 10% of the time.

[bonanova]

dgreening points out that the same can be said if the last bullet is slowest.

[bubbled]

dgreening points out that the same can be said if the last bullet is slowest.

So, would that make the floor 19%? 10% for first bullet fastest, and (.9 X .1) for last bullet slowest and first bullet not fastest.

If so, that would suggest that total annihilation happens a vast majority of the time, you don't get the first fastest or last slowest.

[jasen]

Sorry, I was misunderstanding the question.

I have VBA create this code, I think this time I'm right

Sub RandomBulletTest()
Dim Anhilated As Integer
Dim Bullets As Variant
Dim AllAnhilated As Single
Dim TotalBullets As Integer
Bullets = Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2)
        
For Cnt = 1 To 1000000
    ''random inisial speed between 0 to 1
    For i = 0 To 9
        Bullets(i) = Rnd
    Next i
    TotalBullets = 10
    ' value -2 for anhilated bullets
ulang:
    For i = 0 To TotalBullets
        If Bullets(i) < Bullets(i + 1) Then
            TotalBullets = TotalBullets - 2
            For j = i To TotalBullets
                Bullets(j) = Bullets(j + 2)
            Next j
            Bullets(TotalBullets + 1) = -2
            Bullets(TotalBullets + 2) = -2
            GoTo ulang
        End If
    Next i
finish:
        'check how many bullet anhilated
        For i = 0 To 9
            If Bullets(i) < 0 Then
                Anhilated = Anhilated + 1
            End If
        Next i
        
        'test wheather all bullet anhilated or not
        If Anhilated = 10 Then
            AllAnhilated = AllAnhilated + 1
        End If
        Anhilated = 0
    Next Cnt
    Selection.TypeText Text:=" P of all anhilated = " + str(AllAnhilated / 1000000)
End Sub

--------------------------

3 times running the code the results are

P of all anhilated =  0.245612 
P of all anhilated =  0.245541 
P of all anhilated =  0.246631

so I conclude the probability is 24.6 percent

 

[jasen]

And for 4 bullets are

P of all anhilated =  0.374813
P of all anhilated =  0.374194 
P of all anhilated =  0.375763

so I conclude the probability is 37.5 percent

 

Edited September 2, 2015 by jasen

[CaptainEd]

I'm surprised that the choice of annihilation is so simple as these programs suggest. Perhaps there's a constraint I haven't comprehended yet. Suppose the bullets fired on one second intervals are b0, b1, b2, and b3, And suppose their velocities are v0, v1, v2, v3. Even the 4-bullet case seems to have several outcomes, one of which is that b2 catches b1 before b1 catches b0. Nowhere in these code bodies is there a three-bullet comparison. In fact, even that comparison isn't quite enough, as it's possible that b3 could catch b2 before b1 catches b0. 

Am I missing something in the code? or am i missing something in the problem? 

Edited September 2, 2015 by CaptainEd

[CaptainEd]

My Monte Carlo for zilch-4 yields 0.357.

We don't have to simulate second by second, as there are closed forms for the collision times. What we do need Monte Carlo for is probability assignments.

Bullets b0, b1, b2, and b3 are fired at times t = 0, 1, 2, 3 with velocities v0, v1, v2, v3

Using this fixed time scale, distances traveled by each bullet as a function of t are:

s0 = v0 * t
s1 = v1 * (t - 1)
s2 = v2 * (t - 2)
s3 = v3 * (t - 3)

by equating the distances traveled by two bullets, we learn potential collision times

(t10): v0*t0 = v1 ( t10 - 1), etc.

t10 = v1 / ( v1 - v0 )
t21 = (2*v2 - v1) / (v2 - v1)
t32 = (3*v3 - 2*v2) / (v3 - v2)
t30 = 3 * v3 / (v3 - v0)

if any of these times are negative or has a zero denominator, there will be no such collision. 

Since we want to know P(all annihilate), there are the following cases
== (21)(30)
* (t21 < t32) & (t30 exists) & (t21 < t10 if t10 exists)

== (10)(32)
* (t10 < t32) and (t10 < t21 if t21 exists)
* (t32 < t10) and (t32 < t21 if t21 exists) 

All other cases result in (10 only), (21 only), (32 only), or (no collisions at all)

So, evaluating these by Monte Carlo sampling:

generated 4 random numbers, uniformly distributed 0,1, evaluated "allgone", 1000 such samples, got 357 allgones. I get P(zilch) = 0.357, but I sure can't imagine a closed form

[CaptainEd]

I've run 20000 samples, with p(zilch-4) of 0.319

[CaptainEd]

Error! I left out a case: corrected cases are:

== (21)(30)
* (t21 < t32 if t32 exists) & (t30 exists) & (t21 < t10 if t10 exists)

== (10)(32)
* (t10 < t32) and (t10 < t21 if t21 exists)
* (t32 < t10) and (t32 < t21 if t21 exists) 

 20000 samples of this yields 0.371. This is close enough to bonanova's statement of 3/8 being spot on, that I'm looking forward EAGERLY to the simple analytical explanation :-)

 

[bubbled]

Error! I left out a case: corrected cases are:

Hidden Content

 20000 samples of this yields 0.371. This is close enough to bonanova's statement of 3/8 being spot on, that I'm looking forward EAGERLY to the simple analytical explanation :-)

 

You need to be careful during the firing phase. I don't think you'll get an accurate result if you just stick the bullets (either 4 or 10) out there with positions and velocities. Some of them may not be there by the time all bullets have been fired. You need to simulate each second of the firing phase to determine which bullets are where as each bullet is fired. 

[jasen]

Error! I left out a case: corrected cases are:

Hidden Content

 20000 samples of this yields 0.371. This is close enough to bonanova's statement of 3/8 being spot on, that I'm looking forward EAGERLY to the simple analytical explanation :-)

 

CaptainEd, before creating the code above, I also thinking like you, but then I reliaze the question is not that hard.

Look at again at prop 1 and 2

1. Every second, a gun shoots a bullet along a straight line.
2. Each bullet has a random speed between 0 and 1   ----> I guest bonanova means 0 m/s to 1m/s (not 0 to invinity)

which means that if  V3> v2 > v1 then second bullet will hit first bullet, before third bullet fired.

[bubbled]

Error! I left out a case: corrected cases are:

Hidden Content

 20000 samples of this yields 0.371. This is close enough to bonanova's statement of 3/8 being spot on, that I'm looking forward EAGERLY to the simple analytical explanation :-)

 

CaptainEd, before creating the code above, I also thinking like you, but then I reliaze the question is not that hard.

Look at again at prop 1 and 2

1. Every second, a gun shoots a bullet along a straight line.
2. Each bullet has a random speed between 0 and 1   ----> I guest bonanova means 0 m/s to 1m/s (not 0 to invinity)

which means that if  V3> v2 > v1 then second bullet will hit first bullet, before third bullet fired.

 

 

This last statement I disagree with. If v1 is .5 and v2 is .51 and v3 is .99, v3 will annihilate v2 first.

at time 0: b1 at 0

at time 1: b2 at 0, b1 at .5

at time 2: b3 at 0, b2 at .51, b1 at 1.0

at time 3: b3 at .99, b2 at 1.02, b1 at 1.5

at time 4:  b1 at 2.0 and b3 and b2 have collided.

[CaptainEd]

I agree with bubbled about Jasen's statement:

:

Jasen, I disagree with your statement that v3>v2>v1 implies that v2 catches v1 before v3 catches v2.
Sometimes it does, but sometimes it does not.

Here are two cases:
v3, v2, v1 are .8, .5, .2
at time t0, we shoot v1
at time t0+1, v1 is .2 m away and we shoot v2
at time t0+1.667, v1 is .2(1.667) m away, and v2 is .5(.667) m away
v1 is .3333 m away, v2 is .333 m away. In other words, 2 catches 1 before we even shoot v3

v3, v2, v1 are .6, .11, .1
at time t0, we shoot v1
at time t0+1, v1 is .1 m away and we shoot v2
at time t0+2, v1 is .2 m away, v2 is .11 m away, and we shoot v3
at time t0+2.22449, v1 is 2.22449 m away, v2 is .11*1.22449 away, v3 is .6*.22449 away
v2 and v3 are both 1.346894 m away, so 3 catches 2 before 2 catches 1

So we can't assume that v3>v2>v2 implies that v2 catches v1 and v3 goes free.

Bubbled, I agree that you have to recognize that bullets disappear, but I disagree that you have to simulate each second; merely calculate collision timestamps

So I calculate all the collision timestamps first, THEN I have to cancel out bullet pairs that self-annihilate. 
look at the cases above:
( 1 ) v3, v2, v1 are .8, .5, .2
t10 = 1.66667
t21 = 3.66667
In this case, t10 collision happens before t21, so 0 and 1 are gone before 2 can catch 1.

( 2 ) v3, v2, v1 are .6, .11, .1
t10 = 11
t21 = 2.22449
In this case, the t21 collision happens before t10, so 2 and 1 are gone before 1 can catch 0.