A convex puzzle

Posted on: August 24th, 2013 by
3

Suppose n points are selected independently and uniformly at random on a line segment of length 1. These n points divide the line segment into n+1 segments. What is the probability that it is possible to rearrange these n+1 segments into a convex polygon?

- via ST Aditya at Stanford

3 Responses to A convex puzzle

I am not certain but I think the answer is 1-1/2^n.

It is well-known that it is possible to form an n-gon with n given segments iff none of these segments is longer than the sum of the remaining ones. To see this, imagine the n-segments connected together and as chords on a large circle. Then shrink the circle until the opposite ends meet. This n-gon is also convex.

So the probability is the same as there being no segment of length 1/2 without a point being selected or 1 minus the probability that there exists a segment of length 1/2 without a point being selected. Since all possible segments of length 1/2 are equally likely, the probability of all points being in the remaining portion is 1/2^n. Thus the probability is 1-1/2^n.