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% ..

 

 

[dburns]

9/24 and 81/3628800

Edited August 21, 2015 by dburns

[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.

[bubbled]

This is what I get with about 1M simulations.

 

All bullets are annihilated approximately 24% of the time

[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

[harey]

I hope I got it:

General idea: As long as the first bullet in line is not the fastest, there will be a collision leading to a system of (n-2) bullets. p(the first bullet in line is never the fastest) is not so hard to calculate.

More in detail: Let's suppose the bullets move from left to right and that the rightmost bullet is numbered bullet_1. When reading, think of a convenient n, something like 8 or 12.

There are two possibilities:

A1) bullet_1 is the fastest, it will not be reached by any other, p=1/n, all hope is lost.

B1) bullet_1 is not the fastest, p=(n-1)/n

There WILL BE a collision. (It does not matter whether bullet_1 is involved or not, whether the slowest bullet is involved or not...) After the collision, we still have (n-2) bullets. If necessary, the rightmost is renumbered as bullet_1.

Again, there are two possibilities:

A2) bullet_1 is the fastest, it will not be reached by any other, p=1/(n-2). [There are (n-2) bullets now.)]

B2) bullet_1 is not the fastest, p=(n-3)/(n-2). [There are (n-2) bullets now.)]

There WILL BE a collision. (It does not matter whether bullet_1 is involved or not, whether the slowest bullet is involved or not...) After the collision, we still have (n-4) bullets. If necessary, the rightmost is renumbered as bullet_1.

Again, there are two possibilities:

A3) ...

B3) bullet_1 is not the fastest, p=(n-5)/(n-4).

This will continue until B(n/2) and no more bullets left.

To annihilate all bullets, must occur B1 and B2 and B3 and    and B(n/2).

p(annihilation)=p(B1) * p(B2) * p(B3)=
(n-1)/n  *  (n-3)/(n-2)  *  (n-5)/(n-4)  *    * (1/2)

Writing backwards, the conjectured formula: (1/2)*(3/4)*(5/6)*  *(n-1)/n.

Surprisingly, it does not matter whether the bullets are shut in regular intervals or not.

[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

[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

[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.

[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.

[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.