The center lies within ....

Probability Level 5

Pick $7$ points at random on the circumference of a unit circle. The probability that the center of the circle lies within the (unique) convex polygon defined by these $7$ random points is $\dfrac{a}{b}$ , where $a$ and $b$ are positive coprime integers.

Find $a + b$ .

The answer is 121.

2 solutions

Brian Charlesworth
Aug 13, 2014

The center of the circle will not lie within the polygon if and only if all $7$ points lie on the same semicircle. So my approach will be to find the probability that the $7$ random points do lie on the same semicircle, and then subtract this value from $1$ to find the probability that the center does lie within ....

I'll do the analysis for $n$ points in general. First choose any one of the $n$ points. Now for each of the other $(n - 1)$ points the probability that they are within $\pi$ radians going clockwise of the chosen point is $\frac{1}{2}$ , and so the probability that all the remaining $(n - 1)$ points lie on the (clockwise) semicircle that has the initially chosen point as the 'leftmost' point is $(\frac{1}{2})^{(n - 1)}$ .

Since the choice of the initial point was arbitrary, this result holds for each of the $n$ points on the circle, and since these events are disjoint, (i.e., we can't have two different points serving as the leftmost point of the clockwise semicircle on which all $n$ points lie), we can simply sum these $n$ probabilities to find that the probability that all the points lie on the same semicircle is $n * (\frac{1}{2})^{(n - 1)}$ .

When $n = 7$ this comes out to $\frac{7}{64}$ , and so the probability that the center of the circle does lie within the convex polygon is $1 - \frac{7}{64} = \frac{57}{64}$ .

Thus $a = 57, b = 64$ and $a + b = \boxed{121}$ .

As a curiosity, the probability of all $n$ points lie on the same semicircle can be expressed as a product of sines: $\prod_{k=1}^{n-1}\sin\frac{k \pi}{n} = \frac{n}{2^{n-1}}$

Tunk-Fey Ariawan - 6 years, 10 months ago

Thanks for sharing that fact. This is a "curiosity" that is useful to remember. (Not sure how to prove it, though.)

Brian Charlesworth - 6 years, 10 months ago

Anyway, the general solution of this problem is also the same as the probability of breaking a stick of length $1$ with an interval broken at $n-1$ points chosen uniformly at random which can be rearranged to form an $n$ -gon.

Tunk-Fey Ariawan - 6 years, 10 months ago

Is this a coincidence? If not, can you explain how the product of trigonometric functions is related to the probability?

Calvin Lin Staff - 6 years, 10 months ago

I don't know either is this a coincidence or not. It looks like I have made a wrong statement, it should have written as "is also equal to" not "can be expressed as". I myself approach this problem using math-stat: maximum of a sample from a uniform distribution, $Y=\max[X_1,\cdots,X_{n-1}]$ , where $X_i$ is a random variable that denotes angle of circular sector formed by $2$ random points and $X_i\sim\mathcal{U}(0,2\pi)$ . I am not that good at probability argument.

Tunk-Fey Ariawan - 6 years, 10 months ago

Nice probability argument. This reminds me of Putnam 2005 A6, where most people solved it by doing the (insane) multi-dimensional integration, instead of finding the "conditional probability" / "count by cases" argument.

Calvin Lin Staff - 6 years, 10 months ago

Thanks. I was familiar with the 'points on a semicircle' problem so I tried to 'disguise' it this way. Little did I realize that the disguise made it resemble a Putnam question. Oh well... As for how "most people solved it", I'm essentially lazy and only use multi-dimensional integration as a last resort. :)

Brian Charlesworth - 6 years, 10 months ago

Oh, it's quite a different question, though with a similar setup. It is slightly harder, but otherwise a relatively easy A6 if you choose a suitable approach. The question is

Given $n\geq 4$ points selected at random on the circumference of a unit circle, what is the probability that the convex hull of the points contains an acute angle?

Calvin Lin Staff - 6 years, 10 months ago

@Calvin Lin – Yes, that would have a similar setup, but because there could be two acute angles we would have to work out that probability and then do some inclusion/exclusion. Ugh... Well, it beats multi-dimensional integration, anyway. :)

Brian Charlesworth - 6 years, 10 months ago

@Brian Charlesworth – The two acute angles case is actually easy to deal with, after you study. PIE doesn't need to be involved.

Calvin Lin Staff - 6 years, 10 months ago

Kindly tell why have multiplied by n

Sushant Vijayan - 6 years, 10 months ago

For each of the $n$ points, the probability that it is the leftmost point of the clockwise semicircle is $P = (\frac{1}{2})^{n - 1}$ . Now since there can be only one leftmost point of the clockwise semicircle, these events, (and by event I mean the case where the $k$ th point going clockwise is the leftmost point, where $1 \le k \le n$ ), are mutually disjoint, i.e., none of them intersect with any of the other events.

Now recall that for mutually disjoint events, the probability of their union is just the sum of the probabilities of the individual events. Since each of the $n$ events occurs with probability $P$ , the probability of their union is just $n*P$ .

This link may help explain this concept better.

Brian Charlesworth - 6 years, 10 months ago

Thank you.Your definition of event cleared things up.

Sushant Vijayan - 6 years, 10 months ago

Bob Kadylo
Jul 26, 2018

See here for more information

The center lies within ....

The answer is 121.

2 solutions

0 pending reports