11
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Welcome to MSE! Can you explain what you've tried and say where you're having trouble? What results do you know that might be helpful? $\endgroup$
    – user296602
    Commented Dec 29, 2015 at 17:50
  • 1
    $\begingroup$ I started from 3 points, to 6 points, 9 etc. However I cannot see the link between the probability of forming acute triangle and the position/number of points. $\endgroup$
    – Steve
    Commented Dec 29, 2015 at 17:53
  • $\begingroup$ I know that there is a result stating that choosen $3$ random points in the plane the prob that they form an acute triangle is $1/4$. I don't know if it is related. $\endgroup$
    – mrprottolo
    Commented Dec 29, 2015 at 17:55
  • $\begingroup$ Unless this comes directly from a contest, I rather like posts that are posed as a challenge problem. I think, however, that I am in the minority in that opinion among MSE users; the prefer the "I tried this and I am stuck" sort of problem. $\endgroup$ Commented Dec 29, 2015 at 18:13
  • 2
    $\begingroup$ Note that this problem (if the statement to be proven is indeed true!) is not at all a probability problem; that is a mis-tagging. $\endgroup$ Commented Dec 29, 2015 at 18:15

4 Answers 4

9
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ You are giving excellent references to a problem other than that posed by the PO. He asks for a proof that at most 70% if the triangles formed are acute; it is irrelevant that with random distribution the acute fraction tends to be much less than 70%. For example, with five points, one can easily place the points such that 7 out of ten triangles are acute [e.g. at (-5,1), (0,0), (5,1), (-1,100), (1,100)] yet if you place the points by any intuitively "random" process the chances of 7 acute triangles are remote. $\endgroup$ Commented Dec 29, 2015 at 20:22
  • $\begingroup$ If it's true, then it has to be true for 100 points chosen at random in a compact region. $\endgroup$
    – BruceET
    Commented Dec 29, 2015 at 20:35
  • $\begingroup$ @BruceET: Yes, of course. But the converse doesn't hold, so your answer is irrelevant. $\endgroup$
    – TonyK
    Commented Mar 18, 2016 at 20:32
  • $\begingroup$ In this question math.stackexchange.com/questions/2892862/… I give a solution with $5/9$ of the triangles acute. It is more than $50\%$. Points have neighbours that are many orders of magnitude closer than the pattern's diameter so a random search is not going to find it. $\endgroup$
    – Empy2
    Commented Oct 1, 2018 at 11:59
0
$\begingroup$

Let $\nu (n)$ be the number of points among the $n$ points that form a convex polygon. Denote by $P_1, P_2, \cdots$ these points in clockwise direction. Also, let $O$ be the excentre of the polygon. For the sake of circular direction, assume that if $i + j > \nu (n)$ then $$P_{i + j} = P_{i + j - \nu (n)}$$ for any $i, j < \nu (n)$. Form a quadrilateral $O P_i P_j P_k$, then $\angle P_i O P_k$ will be obtuse if $k - i \geqslant 4$, thus making the triangle $P_i P_j P_k$ acute. Then, the number of the acute triangles that can be formed by $P_1, P_2, \cdots$ is equal to the number of configurations $P_i P_j P_k$ where $j - i \geqslant 2$ and $k - j \geqslant 2$, and this in turn equals $$2 {{\nu (n) - 4} \choose {2}} = (\nu (n) - 4) (\nu (n) - 5).$$

Consider now the $n - \nu (n)$ points inside the polygon, and denote them by $Q_1, Q_2, \cdots$. There are three cases:

(1) one point from the inside and two points from the vertices, of the polygon. Observe that $\angle P_i Q_j P_k$ with $k > i$ being an acute angle guarantees that the triangle $Q_j P_i P_k$ is acute, which is guaranteed by that there are at least $5$ couples of points $(P_i, P_k)$ that can be separated, for $4$ couples will include right angles. The number of such acute triangles is $$\geqslant 2 \sum_{i = 5}^{n - \nu (n)} {{\nu (n) - 1} \choose {\nu (n) - i}}.$$

(2) two points from the inside and one point from the vertices, of the polygon. Analogous argument.

(3) three points from the inside of the polygon. This one is difficult.

Don't blame me please if you think my reasoning is wrong or otherwise not good. I am not a geometer. The sole reason that this problem attracted me is its elementary nature.

$\endgroup$
4
  • $\begingroup$ if the three points lie on the boundary of a circle whose center is contained inside the triangle. $\endgroup$ Commented Dec 29, 2015 at 21:17
  • 1
    $\begingroup$ The hint brings one no closer to the proof. The first statement is a triviality, the second, about circumstances, turns out to be a red herring except as a starting point for very low numbers of points. $\endgroup$ Commented Dec 29, 2015 at 21:47
  • $\begingroup$ I posted a (partial) solution. Check it out. Happy Yalda to everyone! $\endgroup$
    – user98186
    Commented Dec 30, 2015 at 16:21
  • 1
    $\begingroup$ @ForeverMozart I never thought of that. I wish I thought of that before so I could use it in my solution. My acute condition is a lot harder and far less elegant. Too late now, I'm too tired. $\endgroup$
    – user98186
    Commented Dec 30, 2015 at 16:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .