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

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.

I am still not certain of the reasoning but an explanation that seems reasonable and matches experimental data for n=2,3,4 is 1-(n+1)/2^n.

Almost surely no segments of the same length will be formed. So if we want the largest segment first, there are n! ways of the (n+1)! ways to rearrange the segments. Then the probability that all n points are chosen past the 1/2 point is 1/2^n. Thus the probability of failing is (n+1)!/n!/2^n = (n+1)/2^n.

View this related puzzle.