Another week, another riddler. This weeks:
From Keith Wynroe, a concise circular conundrum:
If N points are generated at random places on the perimeter of a circle, what is the probability that you can pick a diameter such that all of those points are on only one side of the newly halved circle?
What a cool problem. First, I wanted to restate the problem so it could be evaluated more easily. I came up with finding the maximum difference in angle between two points. If this value is greater than 180 deg then you can draw a diameter in there that would satisfy this criteria.
Now how do we figure out how often this criteria is met? First, lets assume that one point is always at 0 (we can achieve this by rotating our circle). The same point is also at 360 degrees. Then there are N-1 points that will be located on the rest of our circle
For N=3 this would look like:
This is what it may look like after the points are placed. However, before points B & C are placed we have
If we place B & C and both are 180 deg or further from A1 then our layout would pass the test (shown in yellow). This is our first condition for creating a passing circle. For this experiment lets say we don’t and we place B between 0 and 180 degrees and instead get something like this:
Now, if we placing C and its greater than 180 degrees larger than B or less than B it would pass the test (shown in yellow). This is our second condition. Lets again say we don’t place it there and get something like this:
This brings us to our final condition, if all points are 180 deg or greater from A2. In this case they are, so our circle passes the test.
Reviewing: our conditions are
1: All points are 180 deg away from A1.
Probability (1/2)^(N-1)
2: All points are 180 deg away from B.
Probability (1/2)^(N-1)
3: All points are 180 deg away from A2.
Probability (1/2)^(N-1)
Because these are independent we can sum them and get the chance of success as 75 for N = 3. Generalizing, we get:
The only thing that changes with an increased number of points is that there are more “Condition 2″s for each additional point – which gives you the N value on