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

Post a reply
Username
Message body

 Emoticons View more Emoticons
 [quote="Laramie"]ralphmerridew is correct, but there is an elegant proof of that for all n.[/quote]
Options
HTML is OFF
BBCode is ON
Smilies are ON
 Disable BBCode in this post Disable Smilies in this post

 All times are GMT
 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
 Topic review
Author Message
esme
Posted: Mon Feb 18, 2013 10:34 am    Post subject: 1

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.
Thok
Posted: Mon Feb 18, 2013 12:59 am    Post subject: 0

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
Posted: Mon Feb 18, 2013 12:25 am    Post subject: -1

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?
L'lanmal
Posted: Sun Feb 17, 2013 2:57 am    Post subject: -2

Well, I for one am ready to see your answer.
Laramie
Posted: Thu Mar 31, 2011 2:42 am    Post subject: -3

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
Posted: Tue Mar 29, 2011 12:20 am    Post subject: -4

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
Posted: Mon Mar 28, 2011 11:28 am    Post subject: -5

ralphmerridew is correct, but there is an elegant proof of that for all n.
ralphmerridew
Posted: Mon Mar 28, 2011 3:23 am    Post subject: -6

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
Posted: Sun Mar 27, 2011 11:58 pm    Post subject: -7

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.
L'lanmal
Posted: Sun Mar 27, 2011 11:16 pm    Post subject: -8

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.
Zag
Posted: Sun Mar 27, 2011 9:44 pm    Post subject: -9

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).
Laramie
Posted: Sun Mar 27, 2011 8:58 pm    Post subject: -10

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

Powered by phpBB © 2001, 2005 phpBB Group
Site Design by Wx3