Search

 
Problem Description

Yes J! 

No L 
Three points are placed randomly on the circumference of a circle.
What is the
probability that all three points lie within the same semicircle?
Background & Techniques
Here's a simple puzzle that I found challenging to solve (like a week's worth
of spare time challenging). It's from my
Sit & Solve® Brainteasers (Sit & Solve® Series) book received as a gift from one my children. My
first analysis incorrectly concluded that the the odds were 5050 even though my
simulated seemed to confirm it. The sticking point is in accounting for
the looparound effect when points near the high end of the range are close
those near the low end.
Analytical Solution (Corrected)
Given N random points on a circle, we can rotate one of the points back to
lie at 0 degrees by subtracting the its value from each of the N values. Now the
probability that we have a solution based on the first point semicircle is the
probability that the other N1 points all fall either to the left or right of
the line from 0.0 and it's semicircle end point at 180 degrees. The probability
of a single point falling on a particular side is 1/2 and the probability of all
occurring is the product of the N1 probabilities or (1/2)^(N1). This
probability applies to each of the semicircles drawn from the N points so the
probability of one or more solution semicircles is N/2^(N1). E.G. for N=3,
P=3/4 = 0.75. For N=4, P=4/8 (=1/2) = 0.500. For N=5, P=5/16 = 0.3125. etc.
Experimental Solutions:
Strategy is to run a simulation with a large number of random point
sets and divide successful outcomes by total experiments to
calculate probability of success. The problem is defining "success"
for each sample. For simplicity, points are generated between 0 and
1, each value represents the fraction of a complete circle moving
clockwise from the top to the point.
 Simulation strategy #1 (Incorrect): Equivalent problem is,
given 3 random numbers between 0 and 1, what is the chance that they are all
less than 0.5 or all greater than 0.5? This fails because of the
"wraparound" effect of point lying on a circle. This causes solutions which cross the boundary
from to 1 to 0 to be missed.

 Simulation strategy #2: (Incorrect): Given 3 random numbers between 0 and 1, sort them ascending
and subtract the smallest from the other 2. This is equivalent of
rotating the points back so the first point is at zero degrees. Now if
the other two are less than (or greater than) 0.5, they fall on the
same semicircle. This has the same problem as strategy #1.

 Simulation strategy #3: (Success!): Given 3 random numbers between 0 and 1, sort them ascending
and temporarily add 1.0 to the lowest value and append it to the
end as the highest value. Now check the gap between each original
value and its next higher neighbor. If any gap is greater than or equal
to 0.5 then all points fall within the other semicircle formed by a
line from this point through the circle center and a solution has
been found. This is the first solution to account for "wraparound".

 Simulation strategy #4 (Success!  no sorting): For the 1st point, mark the point and the point half a circle away
as "start" and "end" points of its semicircle. Check all other points
and flag them as Left or Right of the semicircle based on
whether its value is between the semicircle start and end points or
not After checking, if both left and right have been found, this
semicircle is not a solution, otherwise it is. If no solution has been
found, continue checking semicircles from the other points until one
is found or all semicircles have been checked. 
The program has buttons to run experiments with 1,000,000 trials for each of
these four methods and report successful outcome counts and calculated
probability estimates. The two successful methods were extended to allow
for 2 to 10 random points per circle in each trial and to display results for
the first 100 trials with an option to graphically display the points and
semicircles for selected outcomes.
Running/Exploring the Program
Suggestions for Further Explorations
???
Original Date: April 27, 2015 
Modified:
July 29, 2017 

