The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
Laramie
Daedalian Member

 Posted: Sun Mar 27, 2011 8:58 pm    Post subject: 1 The endpoints of n intervals are randomly chosen in the interval [0,1]. Let P(n) be the probability that each interval is disjoint from at least one of the other intervals. What is P(n)?
Zag
Tired of his old title

 Posted: Sun Mar 27, 2011 9:44 pm    Post subject: 2 Suppose we choose 4 points randomly and label them A, B, C, D, in order of least to most, there are 3 ways in which they can connect into segments: A-B & CD ---- AC & BD ---- AD & BC, with equal probability. Only one of those has no overlap, so P(2) = 1/3. For the next step, I'm not sure. I know I could calculate the chance that U(n), where U(n) is the chances that there are no overlaps at all. But I don't know how to calculate P(n).
L'lanmal
Daedalian Member

 Posted: Sun Mar 27, 2011 11:16 pm    Post subject: 3 Edit: I just reread and realized I missed the word "each" in the original statement. That puts me in a similar boat as Zag: I found the probability that there exists a pair of disjoint intervals. Previous text: I was going to raise the standard objection to "random" not being defined, but most definitions will lead to the same answer in this case. Claim: Take the 2n end points of the n intervals and color each point with a color representing the interval. This gives n colors, with two points each. Then some pair of intervals is non-overlapping if, and only if, of the first n points (in numeric order), two points are the same color. There are [(2n)!] / [(2^n)] ways to make this coloring. There are n! ways of coloring the left half n colors, and n! ways of coloring the right half n colors. Therefore, if the claim holds, P(n) = [(n!)*(n!)*(2^n)] / [(2n)!]. ------------------- Proof of Claim: Suppose two of the first n points are the same color. Then, by the pigeonhole priniciple, some color does not appear in the first n points. These two colors represent non-overlapping intervals. Suppose that all of the first n points are different colors. Then the segment between the nth and (n+1)st point is contained in all intervals. Therefore all intervals overlap.Last edited by L'lanmal on Sun Mar 27, 2011 11:48 pm; edited 1 time in total
Laramie
Daedalian Member

 Posted: Sun Mar 27, 2011 11:58 pm    Post subject: 4 L'lanmal: I do like your proof, but as you noted it is for a slightly different problem. To be clear, suppose that for n=3 and that paired endpoints are denoted A, B, and C. The sequence ABBCCA would represent an overlapping scenario while ABBACC would represent a disjoint scenario.
ralphmerridew
Daedalian Member

 Posted: Mon Mar 28, 2011 3:23 am    Post subject: 5 For n=3: Color the endpoints as described in L'lanmal's method. Let A be the first color, B the second, C the third. Cases: AABBCC yes AABCBC yes AABCCB yes ABABCC yes ABACBC no ABACCB no ABBACC yes ABBCAC no ABBCCA no ABCABC no ABCACB no ABCBAC no ABCBCA no ABCCAB no ABCCBA no P(3) = 1/3. Computer search gives P(n) = 1/3 for n=2,3,4,5,6,7,8,9
Laramie
Daedalian Member

 Posted: Mon Mar 28, 2011 11:28 am    Post subject: 6 ralphmerridew is correct, but there is an elegant proof of that for all n.
L'lanmal
Daedalian Member

 Posted: Tue Mar 29, 2011 12:20 am    Post subject: 7 I'm still looking, off and on. Induction has been difficult, because adding a color can not overlap with previously overlapping intervals, or add an interval that overlaps all of a set of non-overlapping. Knowing that the answer is 1/3rd may help some in the direction of a combinatorial proof.
Laramie
Daedalian Member

 Posted: Thu Mar 31, 2011 2:42 am    Post subject: 8 A hint for anyone still interested: I don't recommend a combinatorial approach (mostly because I needlessly wasted hours on it). Rather, I recommend thinking about how you might label pairs of endpoints in a useful order.
L'lanmal
Daedalian Member

 Posted: Sun Feb 17, 2013 2:57 am    Post subject: 9 Well, I for one am ready to see your answer.
esme
^^^^-- is female! Get the pronouns right

Posted: Mon Feb 18, 2013 12:25 am    Post subject: 10

 Laramie wrote: L'lanmal: I do like your proof, but as you noted it is for a slightly different problem. To be clear, suppose that for n=3 and that paired endpoints are denoted A, B, and C. The sequence ABBCCA would represent an overlapping scenario while ABBACC would represent a disjoint scenario.

Why would ABBACC be a disjoint scenario?
_________________
Mundus vult decipi, ergo decipiatur.
Thok
Oh, foe, the cursed teeth!

Posted: Mon Feb 18, 2013 12:59 am    Post subject: 11

 esme wrote: Why would ABBACC be a disjoint scenario?

The pairs (A,C), and (B,C) are disjoint, so each interval belongs to a disjoint pair.
esme
^^^^-- is female! Get the pronouns right

Posted: Mon Feb 18, 2013 10:34 am    Post subject: 12

Thok wrote:
 esme wrote: Why would ABBACC be a disjoint scenario?

The pairs (A,C), and (B,C) are disjoint, so each interval belongs to a disjoint pair.

Thanks, I didnt read the OP properly.
_________________
Mundus vult decipi, ergo decipiatur.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersesmeL'lanmalLaramieralphmerridewThokZag Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum