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$.
Posted: Aug 29 '12
Seen: 154 times
Last updated: Apr 04
Something is fishy about the second part, for n=4, k=2 I don't get 2/3.
domotorp (Sep 01 '12)editFor n=4, k=2 the answer should be 2/5 which is implied by the formula in the second part.
Shiva Kintali (Oct 19 '12)editMaybe 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).
domotorp (Oct 20 '12)edit