Putnam 2005, Problem A-6

Let $n$ be given, $n \geq 4$, and suppose that $P_1, P_2, \ldots, P_n$ are $n$ randomly, independently and uniformly chosen points on a circle. Consider the convex $n$-gon whose vertices are the $P_i$. What is the probability that at least one of the vertex angles of this polygon is acute?

Solution:
First solution: The angle at a vertex \(P\) is acute if and only if all of the other points lie on an open semicircle. We first deduce from this that if there are any two acute angles at all, they must occur consecutively. Suppose the contrary; label the vertices \(Q_1,\ldots,Q_n\) in counterclockwise order (starting anywhere), and suppose that the angles at \(Q_1\) and \(Q_i\) are acute for some \(i\) with \(3 \leq i \leq n - 1\). Then the open semicircle starting at \(Q_2\) and proceeding counterclockwise must contain all of \(Q_3,\ldots,Q_n\), while the open semicircle starting at \(Q_i\) and proceeding counterclockwise must contain \(Q_{i+1},\ldots,Q_n, Q_1,\ldots,Q_{i-1}\). Thus two open semicircles cover the entire circle, contradiction.

It follows that if the polygon has at least one acute angle, then it has either one acute angle or two acute angles occurring consecutively. In particular, there is a unique pair of consecutive vertices \(Q_1, Q_2\) in counterclockwise order for which \(\angle Q_2\) is acute and \(\angle Q_1\) is not acute. Then the remaining points all lie in the arc from the antipode of \(Q_1\) to \(Q_1\), but \(Q_2\) cannot lie in the arc, and the remaining points cannot all lie in the arc from the antipode of \(Q_1\) to the antipode of \(Q_2\). Given the choice of \(Q_1, Q_2\), let \(x\) be the measure of the counterclockwise arc from \(Q_1\) to \(Q_2\); then the probability that the other points fall into position is \(2^{-n+2} - x^{n-2}\) if \(x \leq 1/2\) and 0 otherwise.

Hence the probability that the polygon has at least one acute angle with a given choice of which two points will act as \(Q_1\) and \(Q_2\) is
\[
\int_0^{1/2} (2^{-n+2} - x^{n-2}) dx = \frac{n - 2}{n - 1} 2^{-n+1}.
\]
Since there are \(n(n - 1)\) choices for which two points act as \(Q_1\) and \(Q_2\), the probability of at least one acute angle is \(n(n - 2)2^{-n+1}\).

Second solution: (by Calvin Lin) As in the first solution, we may compute the probability that for a particular one of the points \(Q_1\), the angle at \(Q_1\) is not acute but the following angle is, and then multiply by \(n\). Imagine picking the points by first choosing \(Q_1\), then picking \(n - 1\) pairs of antipodal points and then picking one member of each pair. Let \(R_2,\ldots,R_n\) be the points of the pairs which lie in the semicircle, taken in order away from \(Q_1\), and let \(S_2,\ldots,S_n\) be the antipodes of these. Then to get the desired situation, we must choose from the pairs to end up with all but one of the \(S_i\), and we cannot take \(R_n\) and the other \(S_i\) or else \(\angle Q_1\) will be acute. That gives us \((n - 2)\) good choices out of \(2^{n-1}\); since we could have chosen \(Q_1\) to be any of the \(n\) points, the probability is again \(n(n - 2)2^{-n+1}\).