Let $n\geq 3$ and $A_1,A_2,\ldots,A_n$ be points on a circle. Find the largest number of acute triangles that can be considered with vertices in these points. G. Eckstein
Problem
Source: Romanian IMO Team Selection Test TST 1999, problem 13
Tags: combinatorics proposed, combinatorics
13.09.2014 09:13
What's answer ? Any solution or idea?
14.09.2014 12:15
Solution. (based on the author's idea) We can assume the points $A_1,A_2,\ldots,A_n$ are ordered counterclockwise on the circle, indexed in $\mathbb{Z}_n$ (thus $A_{mn+k}=A_k$). Denote by $A_iA_j$ the arc of the circle starting from $A_i$ and ending in $A_j$ (in counterclockwise direction). We call an arc {\it non-acute} if $m(A_iA_j)\geq 180^\circ$. Let $x_s$ be the number of non-acute arcs $A_iA_{i+s}$ (having $s-1$ points in the interior). Clearly, $m(A_iA_j)+m(A_jA_i)=360^\circ$, hence at least one of the arcs $A_iA_j$ and $A_jA_i$ is non-acute, and thus we can infer that \[(*)\qquad\qquad x_s+x_{n-s}\geq n\] for every $s=1,2,\ldots,n-1$. Equality holds if and only if there are no diametrically opposite points $A_i,A_{i+s}$. We will count the number of non-acute triangles $A_iA_jA_k$. Clearly, such a triangle has exactly one angle corresponding to a non-acute arc. For each non-acute arc $A_iA_j$ having $s-1$ points in the interior there are $n-s-1$ non-acute triangles $A_iA_jA_k$, for which $\angle A_k $ corresponds to the arc $A_{i}A_j$, namely those with $A_k$ in the interior of the arc $A_jA_i$. It follows the number of non-acute triangles is \[ N=x_1\cdot (n-2)+x_2\cdot (n-3)+\cdots + x_{n-2}\cdot 1+x_{n-1}\cdot 0.\] By regrouping terms and using (*) we obtain for $n$ odd \[N\geq 0\cdot(x_{n-1}+x_1)+1\cdot(x_{n-2}+x_2)+\cdots +\dfrac{n-3}{2}\cdot(x_{\frac{n+1}{2}}+x_{\frac{n-1}{2}})\geq\] \[\geq n\left(1+2+\cdots +\dfrac{n-3}2\right)=\dfrac{n(n-3)(n-1)}8.\] Thus the number of acute triangles is at most \[\dbinom {n}{3} - \dfrac{n(n-3)(n-1)}8 = \dfrac{n(n-1)(n+1)}{24}\] and it can be reached, for example, for a regular $n$-gon. By regrouping terms and using (*) we obtain for $n$ even \[N\geq 0\cdot(x_{n-1}+x_1)+1\cdot(x_{n-2}+x_2)+\cdots +\dfrac{n-4}{2}\cdot(x_{\frac{n+2}{2}}+x_{\frac{n-2}{2}})+\dfrac{n-2}{2}\cdot x_{\frac{n}{2}}\geq\] \[\geq n\left(1+2+\cdots +\dfrac{n-4}2 +\dfrac{n-2}4 \right)=\dfrac{n(n-2)^2}8.\] Thus the number of acute triangles is at most \[\dbinom {n}{3} - \dfrac{n(n-2)^2}8 = \dfrac{n(n-2)(n+2)}{24}\] and it can be reached, for example, for an almost regular $n$-gon (with no diametrically opposite vertices).
14.09.2014 13:16
Very nice solution ! Thank you very much mavropnevma.
18.09.2014 20:04
Another approach. The idea is first to determine the conditions the extremal configuration should satisfy and then to calculate the number of acute triangles it contains. Assume $A_1,\ldots, A_n$ is an extremal configuration with maximal number of acute triangles. Let's denote $M=\{A_1,A_2,\ldots,A_n\}$ and for $A\in M $, $A'$ be the antipodal point of $A$. Then $A'\not\in M$, since otherwise we can slightly move $A'$ increasing the number of the acute triangles. We are going to prove that the number of points in each of the two semicircles formed by $A, A'$ are almost the same. More precisely, if $AB$ denotes the arc of the circle starting from $A$ and ending in $B$ in counterclockwise direction, we have: \[ |\,\#\{X\mid X\in M, X\in AA'\}- \#\{X\mid X\in M, X\in A'A\}\,|\le 1 \] for every $A\in M$. Assume on the contrary it's not true and let $\#\{X\mid X\in M, X\in A'A\}> \#\{X\mid X\in M, X\in AA'\}+1$. Let $B_1 \in M$ be the next to $A'$ (counterclockwise) and $B\in M$ next to $A$. Suppose $m(A'B_1) < m(AB) $ Then if we take $B_1$ and place it slightly next to $A'$ in clockwise direction, we will get a new configuration with more acute triangles, contradiction. Consider now the case $m(A'B_1) \ge m(AB) $. But then $\#\{X\mid X\in M, X\in B'B\}> \#\{X\mid X\in M, X\in BB'\}+1$ will also hold, and proceeding, we eventually will get a contradiction. It remains a routine calculation of the number of the acute triangles.