Log In

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

  1. Kevin Chen had this to say about that:

    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.

    • Kevin Chen had this to say about that:

      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.

  2. admin had this to say about that:

    View this related puzzle.


{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}