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

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.

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.

This is a discrete variation of a more general problem that has been around for a while. Here is a very brief historical summary, with some comments.

In 1893 Charles Dodgson, writing as Lewis Carroll, published a collection of "Pillow Problems" that he said he had pondered while in bed with insomnia. One of these was: "Three points are taken at random on an infinite plane. Find the chance of their being the vertices of an $obtuse$-angled triangle." [Ref: Carroll, L. (1893). Curiosa Mathematica, Part II: Pillow Problems. MacMillan, London.]

This is not a well-posed problem because there exists no uniform distribution over the entire plane. Your problem gets around this difficulty by focusing on only 100 points.

Taking a fixed horizontal segment to be the longest side of a triangle and choosing the third vertex at random within the allowable region, he obtained the answer $3\pi / (8\pi – 6\sqrt{3}) \approx 0.64.$ However, another solution based on taking a fixed horizontal segment to be the second longest side leads to the result $3\pi / (2\pi + 3\sqrt{3}) \approx 0.82.$ This additional formulation of the problem illustrates that there may be many solutions depending on how "randomness" is interpreted.

If one considers a compact set in the plane, such as a circle, square, rectangle, or circumference of a circle, then it is possible to define a uniform distribution on that set. On the circumference of a circle, the intuitive value 3/4 of the probability is correct. Even if an analytic solution to the probability of an obtuse triangle may be elusive, it is possible to simulate this probability to any desired degree of accuracy.

For example, in 1991 Ruma Falk and Ester Samuel-Cahn published results for triangles with random vertices within a circle (.720), a square (.725), an equilateral triangle (.748) and in rectangles of various shapes. None of these results agrees with either of "bogus" results above based on choosing a fixed side and third random point. [Fef: Falk, R., & Samuel-Cahn, E. (2001). Lewis Carroll's obtuse problem. Teaching Statistics, 23(3), 72-75.]

In a 1994 paper Stephen Portnoy gives a brief history of the obtuse-triangle problem, makes some comments on the concept of randomness, and proposes using an uncorrelated multivariate normal distribution to model randomness on the plane. Under this distribution, he shows analytically that the probability of an obtuse triangle is 3/4. [Ref/: Portnoy, S. (1994). A Lewis Carroll pillow problem: Probability of an obtuse triangle. Statistical Science, 9(2), 279-284.]

Scanning the valid results in these papers, plus a few simulation projects my students have tried, I find no case with less that half obtuse, so your statement about acute triangles from 100 points may be true.