Puzzle : Semi-circle covering n points

Well,

This is not much of a puzzle. Actually, it is a problem in continuous probability, in which, I am really not good at. This question was posted by saket.  Sagarmoy and Ramprasad could devise a solution, however, I will only describe RP’s solution because of its simplicity.

Problem :

Given n points drawn randomly on the circumference of a circle, what is the probability they will all be within any common semicircle?

Solution :

One might think that there are infinitely many semi-circle on the circumference of a circle. However, the beauty is that we need to consider only n semi-circle here.

If a semi-circle covering all n points, indeed exists, then, a semi-circle covering all n points and starting from one of the points in a clock-wise direction also exists.

So, given a semi-circle which starts at one of the point in clock-wise direction. The probability that the rest of the n-1 points will be in that semi-circle is \frac{1}{2^{n-1}}. So for n such semi-circle, the probability will be \frac{n}{2^{n-1}}

Such a simple solution!! But we really had a hard time when we were trying to solve, because we were focusing too much on the fact that the probability is continuous here.

Advertisements

Tags: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: