Circular Reasoning

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

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 50-50 even though my simulated seemed to confirm it.  The sticking point is in accounting for the loop-around 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 N-1 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 N-1 probabilities or (1/2)^(N-1).  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^(N-1). 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  "wrap-around" 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 "wrap-around".
     
  • 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: February 18, 2016

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.