Let $M$ be a set of $99$ different rays with a common end point in a plane. It's known that two of those rays form an obtuse angle, which has no other rays of $M$ inside in. What is the maximum number of obtuse angles formed by two rays in $M$?
Problem
Source: 2008 Bulgarian Autumn Math Competition, Problem 8.4
Tags: Geoemtry, combinatorics, Obtuse triangle
Marinchoo
19.03.2022 16:36
I was asked for a solution to this problem, so I'm posting the official one and one consisting of my ideas.
$\textbf{Answer: 3267}$
Obviously, the $99$ rays form $\binom{99}{2}=99\times 49$ angles. These $99$ angles, which don't have a ray inside them, we'll call $\textit{elementary}$. The $\textit{elementary}$ angles have sum $360^{\circ}$, therefore there are no more than $3$ obtuse $\textit{elementary}$ angles and the problem states that there is at least one obtuse $\textit{elementary}$ angle.
If there are $3$ obtuse $\textit{elementary}$ angles, they divide the rays in three sets with $k$, $m$, $n$ rays, where $k+m+n=99$. Note that all angles, formed by two rays of the same set are acute.
If there are $2$ obtuse $\textit{elementary}$ angles, they divide the rays in two groups. At least one of the groups can be contained in an acute angle (let there be $k$ rays in this group) and the other group of rays can be contained in an angle $<180^{\circ}$. Let's divide the rays in this group with the angle bisector of the biggest angle which includes all of them, which we mentioned is $<180^{\circ}$. Let's say the two new groups have $m$ and $n$ rays respectively. Here $k+m+n=99$. Note that all angles, formed by two rays of the same group are acute.
If there's a single $\textit{elementary}$ angle, then all rays are contained in an angle with measure $<270^{\circ}$. We divide this angle into three acute angles and let's denote the number of rays in each group by $k,m,n$ respectively where $k+m+n=99$. Note that all angles, formed by two rays of the same group are acute.
In all cases, the number of acute angles is at least:
\[\frac{k(k-1)}{2}+\frac{m(m-1)}{2}+\frac{n(n-1)}{2}=\frac{k^2+m^2+n^2}{2}-\frac{km+mn+nk}{2}\geq \frac{(k+m+n)^2}{6}-\frac{99}{2}=\frac{99\cdot 33-99}{2}=99\cdot 16\]where we used the well-known inequality $k^2+m^2+n^2\geq km+mn+nk$. The remaining $99\cdot 49 - 99\cdot 16=3267$ angles can be obtuse. This is achieved when we have $3$ $\textit{elementary}$ angles and $k=m=n=33$.
This is more like a walkthrough rather than a solution because we'll present motivation. Let's first name the rays $a_{1},a_{2},\ldots ,a_{99}$ randomly.
The construction jumps out at us when we take for example a ray with endpoint $O$ and rotate it by $120^{\circ}$ and $240^{\circ}$ to get two other rays. After that, taking $32$ rays close to each of those three rays yields a construction with $3\times 33\times 33=3267$ obtuse angles. This seems to be optimal and we wish to prove it. The construction leads us to noticing the following:
$\textbf{Lemma:}$ For any $4$ different rays in $M$ we can find two of them, which don't form an obtuse angle.
$\textit{Proof:}$ Take the $4$ angles formed by these rays which don't have another ray in them. Their sum is $360^{\circ}$, so one of them is $\leq 90^{\circ}$.
Now consider the undirected graph $G(V,E)$ with $|V|=99$. A vertex $v_{i}\in V$ we'll say corresponds to the ray $a_{i}\in M$. We'll have $v_{i}v_{j}\in E$ only if $a_{i}$ and $a_{j}$ form an obtuse angle. Notice that $|E|$ is the number of obtuse angles in $M$. By the $\textbf{Lemma}$, $G$ has no $4$-cliques, that is, $G$ has no $K_{4}$. By Turan's theorem we have that since $G$ has no $K_{4}$, then:
$$|E|\leq \Big\lfloor\frac{2}{3}\cdot\frac{|V|^2}{2}\Big\rfloor=\Big\lfloor\frac{2}{3}\cdot\frac{99^2}{2}\Big\rfloor=33\cdot 99=3267$$Thus we're done since we presented a construction earlier, so the answer is $3267$.
$\textbf{Note:}$ In this solution the two parts, i.e. the construction and the proof of the upper bound are deeply connected. That is, if you first found the construction, the fact that there are three sets of rays, such that any two rays from different sets form an obtuse angle really reminds of the construction of the equality case in Turan's theorem. After that, the only thing left is for the statement from the Lemma to be true, which it trivially is, so this is the upper bound. Conversely, if you were to first find the upper bound, since the equality case for Turan's theorem is unique in the sense of sets, we easily find the general construction from the first solution. Another thing to note is that the second solution proves that equality occurs only if there are $3$ obtuse $\textit{elementary}$ angles, whereas the first one only mentioned that in this case equality occurs.