Ponder This Challenge - May 2014 - Annihilation probability of 1D gun

Ponder This Challenge:

This month's challenge is from Michael Kleber, based on a problem invented by David Wilson.

Every second, a gun shoots a bullet in the same direction at a random constant speed between 0 and 1.

The speeds of the bullets are independent uniform random variables. Each bullet keeps the exact same speed and when two bullets collide, they are both annihilated.

After shooting 20 bullets, what is the probability that eventually all the bullets will be annihilated?

Please supply the answer rounded to the 10th decimal digit.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  The answer for the general n bullet problem is zero if n is odd (n=2m+1) and \Pi_{i=1}^m ((2*i-1)/(2*i)) when n is even (n=2m).

  So for n=20, the answer is (1*3*5*7*9*11*13*15*17*19) / (2*4*6*8*10*12*14*16*18*20) = 46189/262144 = 0.1761970520.

  However, it is not easy to prove this, and several solvers sent us incorrect proofs.

  Note, for example, that the same order of bullet speeds can yield different collision results:

  For example, let's look at two cases of four bullet speeds:

  A. 0.5, 0.65, 0.9, 0.6

  B. 0.5, 0.8, 0.9, 0.6

  In both cases, the permutation order is the same. The first bullet is the slowest, the second is the second fastest, the third is the fastest, and the last is the second-slowest.

  But if we examine the collisions pattern we see that

  A. 0.5, 0.65, 0.9, 0.6 will yield zero bullets (first the 0.9 will run into the 0.65 and then the 0.6 will collide with the first 0.5 bullet);

  and

  B. 0.5, 0.8, 0.9, 0.6 will give two live bullets forever (first the 0.8 will annihilate the 0.5, then the remaining 0.9 and 0.6 will run forever).

  As a result, we are keeping the challenge open for a while to let you send us your proofs.

Solvers

• Oleg Vlasii (04/29/2014 08:11 PM EDT)
• Leandro Araújo (05/01/2014 07:29 PM EDT)
• Arthur Breitman (05/02/2014 04:54 PM EDT)
• Rick Kaye (05/02/2014 05:34 PM EDT)
• John Tromp (05/03/2014 02:19 AM EDT)
• Peter Gerritson (05/03/2014 01:52 PM EDT)
• Mark Stuckel (05/04/2014 04:48 PM EDT)
• Todd Will (05/05/2014 03:35 PM EDT)
• Daniel Bitin (05/06/2014 05:09 PM EDT)
• Balakrishnan Varadarajan (05/05/2014 10:25 PM EDT)
• Bart De Vylder (05/06/2014 08:28 AM EDT)
• Dan Meyer (05/07/2014 04:28 PM EDT)
• Michael Rosola (05/07/2014 08:10 PM EDT)
• Mathias Schenker (05/08/2014 08:06 AM EDT)
• Tim Joseph Clark (05/08/2014 10:59 PM EDT)
• Alexandre Gilotte (05/12/2014 09:53 PM EDT)
• Levent Ertoz (05/12/2014 10:19 PM EDT)
• John Snyder (05/14/2014 04:13 PM EDT)
• Michael Slifker (05/14/2014 06:01 PM EDT)
• Franciraldo Cavalcante (05/16/2014 11:15 AM EDT)
• Brian Bitto (05/17/2014 11:25 AMEDT)
• Amir Sarid (05/17/2014 08:11 PM EDT)
• Antoine Comeau (05/18/2014 02:34 PM EDT)
• Michael D. Moffitt (05/19/2014 10:25 PM EDT)
• Stéphane Higueret (05/22/2014 11:22 AM EDT)
• Gilles-Philippe Paillé (05/22/2014 07:02 PM EDT)
• Gareth Richards (05/23/2014 08:31 AM EDT)
• Cynthia Beauchemin (05/23/2014 10:56 AM EDT)
• Joe Clark (05/24/2014 04:43 AM EDT)
• Jan Fricke (05/24/2014 07:55 AM EDT)
• Olivier Mercier (05/24/2014 03:41 PM EDT)
• Dan Stora (05/27/2014 02:23 PM EDT)
• Liubing Yu (05/28/2014 02:26 AM EDT)
• Phil Benamy (05/29/2014 02:33 PM EDT)
• Chris Shannon (05/29/2014 05:05 PM EDT)
• Ehud Schreiber (05/31/2014 02:27 PM EDT)
• Karl D'Souza (06/01/2014 09:33 PM EDT)