Points on a circle Part two .

[jay_shark]

There are n>=4 points on the circumference of the circle which form a convex n-gon . What is the probability that at least one of the vertex angles of this polygon are acute ?

Apparently there is a very elegant solution to this problem which I haven't quite figured out yet although I'm aware of a more rigorous solution which i'm not very fond of .

Good luck !

[pzhon]

I don't have a solution yet, but here are some ways of restating the problem.

From basic geometry, an inscribed angle is half of the arc it subtends. So, the question is whether there is at least one semicircle covering all but one point. Obviously, if a semicircle contains all of the points, then by moving it we get a semicircle containing all but one.

The subdivisions can be parametrized by a simplex x_i>=0, sum x_i=2pi. The condition that some semicircle contains all but one point means that two adjacent segments add up to at least pi (half of the circle). This can happen either from the largest segment plus another, or the second and third largest segments, or both.

The linear algebra method used before is to consider the space of linear combinations of the points summing to the 0 vector. An angle is acute if restricting the null space to that coordinate hyperplane (linear combinations giving that point weight 0) does not intersect the positive orthant of that hyperplane. So, the question is whether the intersection of the positive orthant hits all sides of the orthant.

[jay_shark]

Thx Pzhon . Your input to some of my posts are very much appreciated !

[T50_Omaha8]

This was the sixth (hardest) problem on the Putnam exam one time, so it will probably take a lot of us a very long time to come up with the "elegant" solution. I myself have been stumpted by this one for a long while.

It seems as though the question to me can be restated:
What is the probability a line can bisect the circle such that either zero or one verticies lie on one side of the bisected line?

It's lemma time to prove the two questions are equivalent, but this restatement sounds much more doable.

For n=4 it must be 1?

[pzhon]

[ QUOTE ]
This was the sixth (hardest) problem on the Putnam exam one time, so it will probably take a lot of us a very long time to come up with the "elegant" solution.

[/ QUOTE ]
Putnam problems almost always can be solved and written up by someone within 30 minutes, even the harder ones numbered A6 or B6. So, even though it is expected to be hard because it was A6 on the 2005 exam, knowing that this was a Putnam problem would have helped to narrow the search for the technique. Many real problems don't come with a guarantee that they can be written up so quickly, with no dependence on excessively complicated calculations (at least by Putnam standards).

Anyway, here is a spoiler. I took a misstep in my first attempt by concentrating on the largest 3 intervals instead of the locations of the acute angles, but the linear algebra approach was on target, and leads to the second solution.

[bigpooch]

I didn't know this was a Putnam problem and this had me
stay up at night when you stated there was an elegant
solution. After two hours (usually I try not to spend
more than an hour to find the right idea), here is my
solution. I didn't spend time on finding anything more
efficient or more "elegant".

[BTW, if this really is a Putnam question, there must be
solutions posted somewhere, so maybe somebody can post a
different "elegant" solution if there is one to be found]

Solution
========

Let P(n) be the probability that the convex polygon formed
by n points uniformly randomly distributed on a circle have
the property of posessing an interior acute angle. As pzhon
noted, this is equivalent to there existing a semicircle for
which there exists only one point. Suppose n>=5. The case
for n=4 is trivial (every quadrilateral that can be
circumscribed by a circle has an acute angle except for the
case of the square, but four random points produce a square
with probability zero; thus P(4)=1).

Let the points on the circle be labelled A[j] for j=1 to n
counterclockwise starting with A[1]. Also denote that A[k]
is the same as A[j] if k and j are congruent modulo n, just
for ease of notation (e.g., A[0] is the same point as A[n]).

The angle formed by A[j],A[j+1] and A[j+2] is acute if
A[j+2] is at least a semicircle away. Now, A[j+1] could be
that far away in the counterclockwise direction as well
(this occurs with probability 1/[2^(n-1)]) or A[j+1] is just
within a semicircle and the other points are not (this
occurs with probability (n-1)/[2^(n-1)]). Altogether, then
A[j] "starts" an acute angle with probability n/[2^(n-1)].

This is true for every j and there are n points.

By inclusion-exclusion, the probability that SOME point
"starts" an acute angle is then [let sigma denote summation
over indices k,k1,k2,... where k1<k2<...]:

P(n)= sigma(P(A[k] "starts" an acute angle)
-sigma(P(A[k1] and P(A[k2] both "start" an acute angle)

since the higher order terms aren't possible (you can't have
more than two acute angles for an inscribed n-gon for n>=5).

For two points to "start" an acute angle, they must be
adjacent (otherwise, there would be two subtended arcs that
sum to over 2*pi, so they would have to overlap), so the
last summation has essentially only n terms.

Case a)
------

If A[j] "starts" an acute angle, then what is the
probability that A[j-1] does also? If A[j+1] is more than
a semicircle away, it always does and from above this
happens with probability 1/[2^(n-1)].

Case b)
------

If not, consider a circle with circumference 2 (so that
A[j+1] may be on an interval of unit length) and denote the
position of A[j+1] by u which is the distance along the
circle away from A[j] so that u is in (0,1) and u is a
uniform random variable. For A[j-1] to "start" an acute
angle, then this point, among the (n-2) other points must
be at least (1-u) away from A[j] or the probability of
all these points being at least far enough so that A[j-1] is
at least a distance of 1 or more from A[j+1] is then
u^(n-2) since all these points are uniform random variables
restricted on the "other half" of the circle.

Then, the probability that A[j-1] "starts" an acute angle is
the integral (from u=0 to 1) {[u^(n-2)] du} which has value
1/(n-1). This is GIVEN that A[j+1] is within a semicircle
away, so that the probability of this occuring is then
[1/(n-1)]*[(n-1)/[2^(n-1)]]=1/[2^(n-1)].

Thus, P(A[j-1) and A(j) both "start"...) is the sum of the
probabilities in a) and b) or 2/[2^(n-1)] and

P(n) = n*(n/[2^(n-1)]) - n*(2/[2^(n-1)]) or

P(n) = n(n-2)/[2^(n-1)].

Anyone care to check this?

[bigpooch]

Thanks for the link. Somehow, I get the impression that
there are even better proofs because of the final answer.

If had known this was a Putnam problem when I started, that
would have at least "encouraged" me somewhat knowing that
the proof wasn't difficult.

[jay_shark]

You mean that the problem would be difficult but the solution would be short ?

Solution two on the page Pzhon provided has to be the simplest solution . No integrals or anything is involved . I'll have to think about it some more to absorb it all in .

[bigpooch]

A very elegant solution and crystal clear!