Suggest a Book

# Random Intervals

Level: Graduate

posted Aug 29 '12

Shiva Kintali
691 1 6 22
http://www.cs.princeton.e...

There are $n$ points on a line. These points are paired up at random to form $n/2$ intervals.

• Prove that the probability that among these intervals there is one which intersects all the others is $2/3$.

• Prove that the probability that among these intervals there are at least $k$ intervals which intersects all the others is $\frac{2^k}{2k+1 \choose k}$. Note that this is independent of $n$.

Source: from book "Mathematical Puzzles: A Connoisseur's Collection"
delete retag edit

## Comments

Something is fishy about the second part, for n=4, k=2 I don't get 2/3.

(Sep 01 '12)edit

For n=4, k=2 the answer should be 2/5 which is implied by the formula in the second part.

(Oct 19 '12)edit

Maybe I misunderstood something, but if n=4, k=2, there are only two intervals. This means that either they are disjoint (no interval intersects all others=1/3) or they are intersecting (both intersect all others=2/3).

(Oct 20 '12)edit

## Stats

Posted: Aug 29 '12

Seen: 154 times

Last updated: Apr 04