wu :: forums « wu :: forums - Gun with infinite bullets » Welcome, Guest. Please Login or Register. Jan 16th, 2022, 4:26pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: ThudnBlunder, Grimbal, william wu, Eigenray, SMQ, Icarus, towr)    Gun with infinite bullets « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Gun with infinite bullets  (Read 8783 times)
foo
Newbie

Posts: 4
 Gun with infinite bullets   « on: Nov 2nd, 2013, 2:15pm » Quote Modify

There's a gun located on an infinite line. It starts shooting bullets along that line at the rate of one bullet per second.
Each bullet has a velocity between 0 and 1 m/s randomly chosen from a uniform distribution.
If two bullets collide (are at the same spot at the same time) they explode and disappear.
What is the probability that at least one of the bullets will infinitely fly without colliding with another bullet?
 IP Logged
jollytall
Senior Riddler

Gender:
Posts: 574
 Re: Gun with infinite bullets   « Reply #1 on: Nov 24th, 2013, 10:43am » Quote Modify

Since nobody is replying let me try.
My gutfeel tells me, that the original question is something that cannot be answered. The event we want to judge the probability of, is not clear. When do we say that the event (i.e. a bullet flew to infinity) happened? At any time it is only flying with a finite speed and if that speed is not 1 (what has a zero probability), then there might come a bullet somewhere later that can still catch it.
Also on the other side, how can we say that no bullet reaches the infinity if there are infinitely more bullets still coming.
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Gun with infinite bullets   « Reply #2 on: Nov 24th, 2013, 11:52am » Quote Modify

on Nov 24th, 2013, 10:43am, jollytall wrote:
 At any time it is only flying with a finite speed and if that speed is not 1 (what has a zero probability), then there might come a bullet somewhere later that can still catch it.
However, as time increases the chance that the intercepting bullet is intercepted before it can intercept the leading bullet increases. It becomes increasingly unlikely that the leading bullet will be intercepted (at least within a given amount of time).

For simplicity we could first consider that we wait for a steady state before shooting the next bullet, i.e. we wait till every bullet that can catch up to any other bullet has done so, so at "steady state" from left to right (if we're firing in that direction) every bullet we encounter goes faster than the previous. To intercept the leading (fastest) bullet, we need to fire at least as many bullets as are already on their way. And some of those are likely to intercept each other.
If we fire a new bullet, it can either add one to the line (if it's slower than the slowest), or remove one from the line (if it's faster than the currently slowest). So it's a bit similar to a random walk here, except they're not even odds (if it was, then we'd expect to get to a state of 0 bullets with probability 1).
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
TimMann
Senior Riddler

Gender:
Posts: 330
 Re: Gun with infinite bullets   « Reply #3 on: Dec 27th, 2013, 2:19pm » Quote Modify

FWIW, it seems to me that the probability is zero. At any given point, the probability is 0 that the most distant bullet has velocity 1. Therefore with some probability greater than 0, a later bullet will catch it. Since we are running the process forever, the probability is 1 that eventually another bullet will catch it.

This is mostly a gut feel too, though. Maybe jollytall is right that the problem doesn't have a well-defined answer.

What about trying to define the problem in terms of limits? We could ask: what's the limit (if any) of the probability that a bullet will eventually reach distance n from the origin as n goes to infinity? Hmm, I'm pretty sure that's 1, though, contradicting my previous guess!
 « Last Edit: Dec 27th, 2013, 2:25pm by TimMann » IP Logged

http://tim-mann.org/
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7517
 Re: Gun with infinite bullets   « Reply #4 on: Jan 1st, 2014, 11:29am » Quote Modify

I did the same reasoning.  But I don't think it is that simple.  It is not enough that a later bullet eventually will be faster.  It must be faster and not meet any other bullet in the way, and it must not be caught by another still faster bullet coming from behind.
 IP Logged
TimMann
Senior Riddler

Gender:
Posts: 330
 Re: Gun with infinite bullets   « Reply #5 on: Jan 9th, 2014, 12:50pm » Quote Modify

I realized that, but ended up getting muddled anyway. It certainly is always possible that the most distant bullet will be caught by a still faster one that manages not to be exploded first by some other bullet. (Well, except for the unique point case where the most distant bullet has velocity exactly 1.) But I carelessly said the probability of a later bullet catching up is nonzero, when actually I don't know what the probability is.
 « Last Edit: Jan 9th, 2014, 12:52pm by TimMann » IP Logged

http://tim-mann.org/
riddler358
Junior Member

Posts: 84
 Re: Gun with infinite bullets   « Reply #6 on: Mar 3rd, 2014, 3:13pm » Quote Modify

i'd like to share my take on this one

i'm thinking it's 0

reasoning
1) let's say at some point we fired some bullet that is "going to infinity", now forget this bullet, we have at least same probability of firing another one that is at least as fast as the first, and infinite tries
2) no matter how far first bullet is, there is always a chance to generate faster bullet for which difference in speed of this 2nd bullet and the 1st one will be infinitely times greater than difference of speed for any faster bullets to come and 2nd bullet
example
let's say 1st is going to infinity with 0,999
we fire at some point bullet with 0,999999999 speed
that 2nd is chasing 1st with difference of speeds 0,000999999
while any faster bullet to come might chase 2nd with at most 0,000000001
 « Last Edit: Mar 3rd, 2014, 3:15pm by riddler358 » IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2844
 Re: Gun with infinite bullets   « Reply #7 on: Mar 4th, 2014, 6:26am » Quote Modify

on Mar 3rd, 2014, 3:13pm, riddler358 wrote:
 i'd like to share my take on this one   i'm thinking it's 0   reasoning 1) let's say at some point we fired some bullet that is "going to infinity", now forget this bullet, we have at least same probability of firing another one that is at least as fast as the first, and infinite tries 2) no matter how far first bullet is, there is always a chance to generate faster bullet for which difference in speed of this 2nd bullet and the 1st one will be infinitely times greater than difference of speed for any faster bullets to come and 2nd bullet example let's say 1st is going to infinity with 0,999 we fire at some point bullet with 0,999999999 speed that 2nd is chasing 1st with difference of speeds 0,000999999 while any faster bullet to come might chase 2nd with at most 0,000000001

But unless the faster bullet is the next bullet fired, there's a good chance that it'll hit one of the intervening bullets first...
 IP Logged
riddler358
Junior Member

Posts: 84
 Re: Gun with infinite bullets   « Reply #8 on: Mar 4th, 2014, 8:08am » Quote Modify

on Mar 4th, 2014, 6:26am, rmsgrey wrote:
 But unless the faster bullet is the next bullet fired, there's a good chance that it'll hit one of the intervening bullets first...

but it's the same chance as for the bullet that is "going to infinity"
 IP Logged
Uberpuzzler

Posts: 1026
 Re: Gun with infinite bullets   « Reply #9 on: Mar 4th, 2014, 8:23am » Quote Modify

What if the very first Adam and Eve bullet is fired at velocity of exactly 1? Since the time interval between the shots is > 0 no other bullet will ever catch up to it. May be the answer then is given the bell curve distribution what is the probability of the very first bullet being fired at velocity 1?
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Gun with infinite bullets   « Reply #10 on: Mar 4th, 2014, 8:50am » Quote Modify

But that's just 0. The probability of any exact value in a continuous smooth distribution is zero.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
rmsgrey
Uberpuzzler

Gender:
Posts: 2844
 Re: Gun with infinite bullets   « Reply #11 on: Mar 5th, 2014, 3:40am » Quote Modify

on Mar 4th, 2014, 8:08am, riddler358 wrote:
 but it's the same chance as for the bullet that is "going to infinity"

If the "going to infinity" bullet catches up with another bullet before the chaser bullet catches up with it, then the chaser is no longer doomed to catch it, so could itself escape to infinity...
 IP Logged
riddler358
Junior Member

Posts: 84
 Re: Gun with infinite bullets   « Reply #12 on: Mar 5th, 2014, 3:05pm » Quote Modify

on Mar 5th, 2014, 3:40am, rmsgrey wrote:
 If the "going to infinity" bullet catches up with another bullet before the chaser bullet catches up with it, then the chaser is no longer doomed to catch it, so could itself escape to infinity...

there is no bullet in front of "going to infinity" bullet, and so called chaser is bullet that is faster than the "going to infinity" one and no bullets are between them, so either chaser catches or gets caught by it's own chaser
 IP Logged
foo
Newbie

Posts: 4
 Re: Gun with infinite bullets   « Reply #13 on: Mar 8th, 2014, 7:55am » Quote Modify

I think I managed to solve the so called "steady state" variant that towr proposed.
However, I did not figure how to make it work for the original riddle.

The proof isn't as elegant or rigorous as you'd hope, but it's the best I could do:

 hidden: I'll mark a steady state of n bullets with velocities p1,...,pn with It helps to imagine the bullets being fired in the left-to-right direction.   The velocities must satisfy pn <= ... <= p1 , otherwise the state is not steady.   Suppose the system is at a state . The next bullet fired will either have velocity p <= pn (with probabilty pn) resulting in as the next state, or p > pn (with probabilty 1-pn) resulting in as the next state   Define f(, i) as the probability that the bullet at index i ( that has velocity pi ) will survive infinitely given that the system is at the state . Denote g(p) as f(

, 1). This is just shorter notation for the probability that a lone bullet with velocity p will survive infinitly.     I'll try to prove that for all p in [0,1): g(p) = 0 This means that for any bullet fired (in a clean state) the probabilty that it will survive is 0 (eventually returning to a clean state). Since unifying a countable amount of events with probabilty 0 results in an event also with probabilty 0, this implies that the probabilty that at least one bullet survives is 0.     Claim 1: If p1 <= p2 then g(p1) <= g(p2)   If a bullet with velocity p1 survives for a certain sequence of velocities then a bullet with velocity p2 will most certainly survive for the same sequence of velocities.     Claim 2: f(, n) = f(, 1) = g(pn)   Every time a bullet is fired, it can only affect the leftmost bullet. Unless the bullet with index n is destroyed there can be no interaction between bullets to its left and to bullets to its right.     Claim 3: f(, 1) = g(p2) + (1-g(p2))*g(p1)   f(, 1) = f(, 2) + (1-f(, 2))*g(p1)   For a state with two bullets there are two distinct cases in which the first bullet survives: 1. The second bullet survives and thus no bullet can destroy the first bullet so it will survive as well. 2. The second bullet is destroyed at some point, in which case we return to the state with the probablity g(p1) for survival.   f(, 2) + (1-f(, 2))*g(p1) = g(p2) + (1-g(p2))*g(p1)   This is direct usage of Claim 2.     Claim 4: For all p2 <= p1 ,  f(, 1) <= g(p1)*(2 - g(p1))   f(, 1) = g(p2) + (1-g(p2))*g(p1) = g(p1) + g(p2) - g(p1)*g(p2)  = g(p1) + g(p2) - g(p1)*g(p2) = g(p1) + (1-g(p1))*g(p2) <= g(p1) + (1-g(p1))*g(p1) = g(p1)*(2 - g(p1))   This is use of Claim 3 with some algebra + Claim 1 for the inequality.     Denote <*, p> as the set of all states where p2 <= p. Define f(<*, p>, 1) as the probabilty for a bullet with velocity p to survive given that there is a bullet behind it with velocity taken uniformly from [0, p].     Claim 5: f(<*, p>, 1) <= g(p)*(2 - g(p))   The upper bound is true for all p2 <= p so we can derive this bound from the law of total probabilty.     Claim 6: g(p) <= p*g(p)*(2 - g(p))   g(p) = Pr[ The next bullet fired has velocity in [0,p] (next state is in <*,p>) ] * Pr[ The first bullet survives | the state is in <*,p> ] = p * f(<*, p>, 1) <= p*g(p)*(2 - g(p))     Claim 7: g(p) = 0 or g(p) <= 2 - 1/p   If g(p) = 0 then the claim is true. Otherwise we can take Claim 6 and divide by g(p): 1 <= p*(2 - g(p)) 1/p <= 2 - g(p) g(p) <= 2 - 1/p     Claim 8: for all p <= 1/2, g(p) = 0   This is a direct result of Claim 7 and g(p) being in [0,1] (since it is a probabilty).

 IP Logged
foo
Newbie

Posts: 4
 Re: Gun with infinite bullets   « Reply #14 on: Mar 8th, 2014, 7:57am » Quote Modify

 hidden: Denote <[a,b], p> as the set of all states where a <= p2 <= b <= p. Define f(<[a,b], p>, 1) as the probabilty for a bullet with velocity p >= b to survive given that there is a bullet behind it with velocity taken uniformly from [a, b].     Claim 9: for all p > 1/2, f(<[0,1/2], p>, 1) = g(p)   Let p2 <= 1/2 <= p be some velocity for the second bullet. f(, 2) = g(p2) (Claim 2) We know that g(p2) = 0 (Claim 8)   Hence, if the state is in <[0,1/2], p> the second bullet will be destroyed with probability 1. So at some point we return to state

in which the first bullet has probabilty g(p) to survive.     Claim 10: f(<[a,b], p>, 1) <= g(p)*(2 - g(p))   Same as in Claim 5. The upper bound is true for all p2 in [a,b] so we can derive this bound from the law of total probabilty.     Claim 11: for all p > 1/2 , g(p) <= (1/2)*g(p) + (p - 1/2)*g(p)*(2 - g(p))   g(p) = Pr[ The next bullet fired has velocity in [0,1/2] ] * f(<[0,1/2], p>, 1) + Pr[ The next bullet fired has velocity in (1/2, p] ] * f(<(1/2, p], p>, 1) =    = 1/2 * g(p) + (p - 1/2) * f(<(1/2, p], p>, 1) <= (1/2)*g(p) + (p - 1/2)*g(p)*(2 - g(p))     Claim 12: for all p > 1/2 , g(p) = 0 or g(p) <= 2 - 1/(2p - 1)   If g(p) = 0 then the claim is true. Otherwise we can take Claim 11 and divide by g(p): g(p) <= (1/2)*g(p) + (p - 1/2)*g(p)*(2 - g(p)) 1 <= 1/2 + (p-1/2)*(2 - g(p)) 1/2 <= (p-1/2)*(2 - g(p)) 1/(2p - 1) <= 2 - g(p) g(p) <= 2 - 1/(2p - 1)     Claim 13: for all p <= 3/4, g(p) = 0   Same as in Claim 8. This is a direct result of Claim 7 and g(p) being in [0,1] (since it is a probabilty).     Claim 14: If we know that for all p <= 1-1/2k , g(p) = 0 then for all p <= 1-1/2k+1 , g(p) = 0   This is basically the same as the previous steps (Claims 9-13), only for the general case. g(p) = Pr[ The next bullet fired has velocity in [0,1-1/2k] ] * f(<[0,1-1/2k], p>, 1) + Pr[ The next bullet fired has velocity in (1-1/2k, p] ] * f(<(1-1/2k, p], p>, 1) =    = (1-1/2k) * g(p) + (p - (1-1/2k)) * f(<(1-1/2k, p], p>, 1) <= (1-1/2k)*g(p) + (p - 1 + 1/2k)*g(p)*(2 - g(p))   If g(p) = 0 then the claim is true, Otherwise we can divide by g(p): g(p) <= (1-1/2k)*g(p) + (p - 1 + 1/2k)*g(p)*(2 - g(p)) 1 <= (1-1/2k) + (p - 1 + 1/2k)*(2 - g(p)) 1/2k <= (p - 1 + 1/2k)*(2 - g(p)) 1/(2k*p - 2k + 1) <= 2 - g(p) g(p) <= 2 - 1/(2k*p - 2k + 1)   for p <= 1-1/2k+1 the expression above is <= 0     Claim 15: for all k, If p <= 1-1/2k then g(p) = 0   This is given by induction with Claim 8 as it's base, and Claim 14 as the induction step.     Claim 16: for all p < 1 , g(p) = 0   This is derived directly from Claim 15 (for large enough k ...).     The probabilty for any bullet to be fired with velocity 1 is 0. Since Unifying a countable amount of events with probabilty 0 results in an event also with probabilty 0, this implies that the probability that at least one bullet has velocity 1 is 0.   Given that no bullet has velocity 1, any bullet has a probability of 0 for survival (g(p) = 0). Since Unifying a countable amount of events with probabilty 0 results in an event also with probabilty 0, this implies that the probability that at least one bullet survives is also 0.

 IP Logged
mykingislonely
Newbie

Posts: 4
 Re: Gun with infinite bullets   « Reply #15 on: Mar 14th, 2014, 7:07pm » Quote Modify

(Complete beginner riddler here. I have no solutions, just some random thoughts)

Great problem! I've been going back and forth to thinking it was 0% or 100% and now I have no clue.

I don't mean to go off-topic on this thread, but I remember some other problem that went something like:

"You are playing a game in which you get 1 point for rolling a 6 and lose 1 point for any other roll. If you keep playing, you should approach -infinite points. After playing a while, you are at -1,000,000 points.
What are the odds of approaching -infinity without crossing 0?"

Somehow I imagine this problem being really similar. The probability in getting to infinity increases after the average  shot (or roll)... but there is always this chance of losing your leading bullet  (or getting to 0).

 « Last Edit: Mar 14th, 2014, 7:07pm by mykingislonely » IP Logged
aicoped
Junior Member

Gender:
Posts: 57
 Re: Gun with infinite bullets   « Reply #16 on: May 1st, 2014, 10:26pm » Quote Modify

I don't think I agree with the proposed solutions, but I know infinity can cause some issues.

If there can be no bullets with speed 1, then there clearly is some maximal speed bullet. while the probability of a given bullet hitting exactly 1 is "zero" the probability of firing a "faster than the fastest bullet also approaches zero with whatever method you use"

The maximal speed bullet has a limit of 1 and the speed of the bullet that reaches infinity by necessity must be the bullet with the limit of 1.

Firing any specific speed bullet has a zero probabilty, but yet a bullet gets fired.

If I said what is your probability to fire a bullet moving at .75 it is still zero. If any bullet you can name is probability zero, but you must fire a bullet of some speed, there is clearly a problem in our formulation of the problem.

I think though since the rate at which our probability of firing a specific bullet with a given probability goes down at the same rate our "accuracy" of measuring bullet speed does as well, then that all cancels and we could solve the problem by using instead of zero to 1 we could use 1 to 100 and see what happens then we could try again with 1 to 1000 and so on. While going from a finite result to infinite is not always possible, I think it is in this case.

If i am way off or if there is a known solution, would someone link me it?
 IP Logged
foo
Newbie

Posts: 4
 Re: Gun with infinite bullets   « Reply #17 on: May 2nd, 2014, 1:29am » Quote Modify

I think that the reason you don't agree with the proposed solution is that you are not familiar with  continuous random variables (as opposed to discrete random variables).

http://en.wikipedia.org/wiki/Probability_distribution

"When a random variable takes values from a continuum, probabilities can be nonzero only if they refer to intervals."

In our case, it means that the probability that a bullet will have a velocity of either 0.75, 0.764539 or 1 is 0. However, the probability that the velocity is between 0.7 and 0.8 is 0.1 since the distribution is uniform.

The proposed solution, if it is indeed correct, only solves the "steady state" variant proposed by towr in this thread. I'm not familiar with any solution for the original riddle.
 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7517
 Re: Gun with infinite bullets   « Reply #18 on: May 2nd, 2014, 7:29am » Quote Modify

IMB's "Ponder This" has a challenge very much related to this one.
http://domino.research.ibm.com/comm/wwwr_ponder.nsf/challenges/May2014.h tml

And from the name of the inventor, I got the following page that proposes a solution a the end.
http://brentmeeker.com/?page_id=48
 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »