Jump to content
BrainDen.com - Brain Teasers
  • 0

Random bullets


bonanova
 Share

Question

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 by bonanova
Give credit to BMAD's earlier puzzle
  • Upvote 1
Link to comment
Share on other sites

Recommended Posts

  • 1

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

 

 

Link to comment
Share on other sites

  • 0

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 by bonanova
Added link to BMAD's earlier bullet puzzle
Link to comment
Share on other sites

  • 0

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

 

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 1

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

 

Link to comment
Share on other sites

  • 0

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 by CaptainEd
Link to comment
Share on other sites

  • 0

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

Link to comment
Share on other sites

  • 0

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 :-)

 

Link to comment
Share on other sites

  • 0

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. 

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...