Posted by Mensen at mathoverflow.net
Very interesting problem (Very difficult actually)
Let's say that I have a onedimensional line of finite length 'L' that I populate with a set of 'N' random points. What is the probability 'p' that the minimum distance between any pair of these points is larger than some value 'k' or an expression for the mean minimum distance (MMD) for a pair of points in the set  referring to the smallest distance between any two points that can be found, not the mean minimum/shortest distance between all possible pairs of points.
Good problem :D ... I am happy!!!
Update (11/12/09): Solution in comments!!
Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)
Subscribe to:
Post Comments (Atom)
Fraction Brainteaser
Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this art...

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tos...

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...
It can be related to the following: Imagine you have n marked cards in a pack of m cards and shuffle them randomly. What is the probability that they are all at least distance d apart?
ReplyDeleteConsider dealing the cards out, one by one, from the top of the pack. Every time you deal a marked card from the top of the deck, you then deal d cards from the bottom (or just deal out the remainder if there's less than d of them). Once all the cards are dealt out, they are still completely random. The dealt out cards will have distance at least d between all the marked cards if (and only if) none of the marked cards were originally in the bottom (n1)d. The probability that the marked cards are all distance d apart is the same as the probability that none are in the bottom (n1)d.
The points uniformly distributed on a line segment is just the same (considering the limit as m →∞). The probability that they are all at least a distance d apart is the same as the probability that none are in the left section of length (n1)d. This has probability (1(N1)d/L)^N.
Integrating over 0≤d≤L/(N1) gives the expected minimum distance of L/(N^21).
:) I am happy!!! :D