How many acute triangles can be formed by 100 points in a plane?

Given 100 points in the plane, no three of which are on the same line, consider all triangles that have all their vertices chosen from the 100 given points.

Prove that at most 70% of those triangles are acute-angled.

Solution 1:

This is from the 1970 International Mathematical Olympiad. You can find the questions here, and the (rather easy) solution to this question here.

It was one of the homework questions for aspirants to the British team for IMO 1978 in Bucharest. I managed to prove an explicit upper bound on the maximum possible proportion of triangles in $n$ points that tends to $2/3$ as $n$ tends to $\infty$. I can't remember what it was, but it is not too hard to work out, using the process described in the following paragraphs.

The proof of the simpler question goes like this: first prove geometrically that every $4$-set (i.e. set of $4$ points) must contain a non-acute triangle, so that at most $75$% of triangles in a $4$-set can be acute. Then argue combinatorially that if you have shown that at most a proportion $p$ of triangles in an $n$-set can be acute, it follows that at most a proportion $p$ of the triangles in an $(n+1)$-set can be acute.

So we immediately get that at most $7\frac12$ of the $10$ triangles in a $5$-set can be acute; and because the number of acute triangles must be an integer, we can bring this down to $7$ out of $10$, i.e. $70$%.

But there is no reason to stop there. The same process gains nothing when passing to $6$-sets, because $70$% of $20$ is an integer; but passing to $7$-sets gives us $70$% of $35$, which is $24\frac12$, which we can bring down to $24$.

So we can define an integer sequence $(s_i)$ by $s_4 = 3$, and $s_{i+1} = \left\lfloor \dfrac{(i+1)s_i}{i-2}\right\rfloor$. This gives us an upper bound on the maximum possible number of acute triangles in an $n$-set. I seem to remember that it is a cubic in $n$, whose exact form depends on $n$ mod $3$. And the proportion $s_n/\binom{n}{3}$ tends to $2/3$.

Note that $s_n$ is not necessarily the maximum possible number of acute triangles in an $n$-set. It just gives us an upper bound. In fact I think that this upper bound can't be attained for large enough $n$ ($n > 6$ perhaps?). I played around with this a bit, but after all it was $37$ years ago, so the details are blurred.

Solution 2:

The proof that for $N \geq 5$ the fraction of acute triangles cannot exceed $\frac{7}{10}$ involves geometric reasoning only for the $N=5$ case, followed by combinatoric reasoning to create a proof by induction.

We start from Lemma 1: If there exists an arrangement of $N$ points (with $N>5$) forming more than $70\%$ acute triangles (that is, more than $\frac{7}{60}N(N-1)(N-2)$ acute triangles), then there exists an arrangement of $N-1$ points forming more than $70\%$ acute triangles (that is, more than $\frac{7}{60}(N-3)(N-1)(N-2)$ acute triangles).

Proof: Start with an arrangement forming the minimum number of acute triangles at or above $70\%$, namely $$ \left \lceil \frac{7}{60}N(N-1)(N-2) \right \rceil $$ acute triangles. These contain $ 3 \left \lceil \frac{7}{60}N(N-1)(N-2) \right \rceil $ instances of vertices in acute triangles; then one of the $N$ points must participate in at most $\left \lfloor \frac{3}{N} \left \lceil \frac{7}{60}N(N-1)(N-2) \right \rceil \right \rfloor $ acute triangles. Remove that point; among the remaining points there are at least $$ 3 \left \lceil \frac{7}{60}N(N-1)(N-2) \right \rceil - \left \lfloor \frac{3}{N} \left \lceil \frac{7}{60}N(N-1)(N-2) \right \rceil \right \rfloor $$ remaining vertices in acute triangles. Thus there are at least $$ \left \lceil \frac{ 3 \left \lceil \frac{7}{60}N(N-1)(N-2) \right \rceil - \left \lfloor \frac{3}{N} \left \lceil \frac{7}{60}N(N-1)(N-2) \right \rceil \right \rfloor }{3} \right \rceil $$ acute triangles. Assume worst case in every round-off; then we can write this as being at least $$ \frac{7}{60}(N-3)(N-1)(N-2) + 2\cdot \frac{7}{60}(N-1)(N-2)-\frac{1}{3} $$ which for $N \>5$ always exceeds $70\%$ of the triangles among the $N-1$ vertices.

Lemma 2: If for any $N>5$ you can form more than $70\%$ acute triangles, then you can form more than $70\%$ acute triangles (that is, at least 8) among five vertices. Proof: Start from $N$ and repeatedly apply lemma 1.

Lemma 3: Among five points, there cannot be more than seven acute triangles.

The proof starts with thew geometric observation that among four points, at most three one of the four triangles can be acute. Now for the five vertices, if you can form eight acute triangles, then either the remaining two triangles share 2 vertices or just one. Assume they share two vertices, $A$ and $B$, and that the third vertices in the triangles are labeled $C$ and $D$. Then four remaining (acute) triangles do not contain vertex $B$, and thus form four acute triangles sharing four vertices, which is impossible. If the two non-acute triangles share only one vertex, say $ABC$ and $ADE$, then the four triangles not involving vertex $A$ are acute, which again leads to the same impossibility.

Theorem: For $N > 5$ at most $70\%$ of the triangles formed by $N$ non-co-linear points can form acute triangles. Proof: Lemma 5 establishes a base for the inductive process implied by lemma 2.

Observation: In fact, among $100$ points you can have no more than $66.675\%$ acute triangles (the actual maximum may be a lot less than that). This is obtained by starting with the assumption of 107812 acute triangles, and iterating the combinatoric reasoning in lemma 1 until you find that for some set of five points there must be at least 8 acute triangles.