I have had a lot of mail about this problem over the years. Some people question the answer, and some admit the answer is right, but that the solution is wrong. Here is my original solution:
For n points choose any given point and evaluate the probability that the other n-1 lie within a semicircle going clockwise. This probability is (1/2)n-1.Given that there are n points to start with the overall probability is n/2n-1. This may seem like an abuse of taking the sum of probabilities, but in this case only zero or one of the events may be true, which eliminates the problem of joint probabilities.
To prove at least the answer is correct, I did ten million trials for various numbers of points on the circle. I assumed the circle to have 32,767 units or degrees. The first point was defined to be at a halfway point, or 16,383. Then a maximum and minimum were taken for the rest of the points. If the difference between the maximum and minimum were less than 16,383 then the trial was considered to be a success. Note that 16,383 is half of 32,767, rounded down. Because of the rounding we should expect a slightly lower number of successes. Here are the results:
Problem 1 Solution
|Number of Points||Actual Successes||Expected Successes|
Several people have written, saying my answer is right, but the solution is wrong. Here is what David Beim of Columbia University wrote to me about it:
There is no doubt that your answer is right, but your reasoning is unsettling because it confounds ex ante with ex post information. We cannot construct the semicircles until the n points have been selected, and then it is too late to determine ex ante probabilities. This kind of mixing can lead to all kinds of paradoxes in probability, as I am sure you know better than I. For one simple example, select a point on a line. Ex ante, the probability of selecting that point is zero; ex post, the probability must have been greater than zero because it happened.
I attach my own solution (PDF 33K) to the problem, in case it is of interest. Incidentally, I would give this problem four stars rather than three --took me days to get it clear!
Per his comment, I did add a star to the difficulty level, it was 3 starts until November, 2008.
This problem has been published in book form in "Contests in Higher Mathematics" by Gabor Szekely, which is a collection of math problems given to the best mathematicians of Poland over the last several decades. The problem (1963 problem 10) is stated as, "Select n points on a circle independently with uniform distribution. Let Pn be the probability that the center of the circle is in the interior of the convex hull of these n points. Calculate the probabilities P3 and P4. I'm told the answer agrees with mine.Michael Shackleford, A.S.A.