Monte Carlo These Points!

Probability Level 5

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

Now $x\%$ of these triangles be acute-angled triangles.

Find the maximum value of $x$ .

The answer is 66.7.

1 solution

Soumava Pal
Apr 15, 2016

Lemma:

Five points are given in the plane such that no three of them are collinear. Then there are at least three triangles with vertices at these points that are not acute-angled.

Proof

We consider three cases, according to whether the convex hull of these points is a triangle, quadrilateral, or pentagon.

(i) Let a triangle $ABC$ be the convex hull and two other points $D$ and $E$ lie inside the triangle. At least two of the triangles $ADB$ , $BDC$ and $CDA$ have obtuse angles at the point $D$ . Similarly, at least two of the triangles $AEB$ , $BEC$ and $CEA$ are obtuse-angled. Thus there are at least four non-acute-angled triangles.

(ii) Suppose that $ABCD$ is the convex hull and that $E$ is a point of its interior. At least one angle of the quadrilateral is not acute, determining one non-acute-angled triangle. Also, the point $E$ lies in the interior of either $ABC$ or $CDA$ hence, as in the previous case, it determines another two obtuse-angled triangles.

(iii) It is easy to see that at least two of the angles of the pentagon are not acute. We may assume that these two angles are among the angles corresponding to vertices $A$ , $B$ , and $C$ . Now consider the quadrilateral $ACDE$ . At least one its angles is not acute. Hence, there are at least three triangles that are not acute-angled.

Now we consider all combinations of $5$ points chosen from the given $100$ . There are $100C5$ such combinations, and for each of them there are at least three non-acute-angled triangles with vertices in it. On the other hand, vertices of each of the triangles are counted $97C2$ times. Hence there are at least $\frac{3(100C5)}{97C2}$ non-acute-angled triangles with vertices in the given $100$ points. Since the number of all triangles with vertices in the given points is $100C3$ , the ratio between the number of acute-angled triangles and the number of all triangles cannot be greater than $1-\frac{3(100C5)}{(97C2)(100C3)}=0.7$ , that is $70\%$ .

Moderator note:

This proof only calculates an upper bound. In order to be the maximum, we need the least upper bound. See the comments to understand why the answer is 66.7.

But how do you know that there exist 100 points, where exactly 70% of them are acute?

You have shown that 70 is an upper bound, but why is it the least upper bound?

Calvin Lin Staff - 5 years, 2 months ago

Because, Sir, in the lemma I have shown that for 5 points the least upper bound for number of non-acute triangles is 3, and it can be checked manually for all possible configurations that is the least bound.

I am not sure, but doesn't that conclude that the value we get after calculating from there is the least upper bound?

Please correct me if I am wrong.

Soumava Pal - 5 years, 2 months ago

Please correct me if I am wrong.

I don't think anyone can correct you before you present an argument.

Peter Byers - 5 years, 2 months ago

It is the least upper bound in the case of 5 points. How do you know that when more points are added, that this still remains the least upper bound? I agree that it is an upper bound, but you haven't shown that it is the least for 100 points.

Calvin Lin Staff - 5 years, 2 months ago

@Calvin Lin – okay, sir i got you now. I will try to prove it. It may take some time though. :)

Soumava Pal - 5 years, 2 months ago

@Soumava Pal – You are actually very close.

Hint: We want all sets of 5 points to satisfy the 70% bound, and then verify that each triangle is counted the same number of times, or at least that we're not over-counting the number of acute triangles.

Calvin Lin Staff - 5 years, 1 month ago

@Calvin Lin – If we are to believe this post , then the correct answer for $100$ points should be no greater than $66.75$ %, and the proportion of acute triangles from $n$ points is bounded above by $\tfrac23$ for large $n$ .

Mark Hennings - 5 years, 1 month ago

@Mark Hennings – I do believe it! Let the maximum possible number of acute triangles formed by an $n$ -set of points be $s_n$ . Then $s_4 = 3$ .

Any triangle in an $(n+1)$ -set will occur in $\binom{n-2}{n-3} = n-2$ of the $n+1$ distinct $n$ -subsets. If we add the totals of all the acute triangles in the $n$ -subsets, each acute triangle will be counted $n-2$ times. Thus the number of acute triangles in an $n$ -set cannot exceed $\frac{(n+1)s_n}{n-2}$ , and hence $s_{n+1} \; \le \; \left\lfloor \frac{(n+1)s_n}{n-2}\right\rfloor \;.$ Then $s_{100} = 107811$ is an upper bound for the number of acute triangles in an $100$ -set, giving a maximum proportion of $66.67$ %. This is even better than the $66.75$ % listed elsewhere in the post.

The correct answer should be $66.7$ (the question did not allow me to enter this, my preferred solution).

Mark Hennings - 5 years, 1 month ago

@Mark Hennings – What happens if we modify the definition of an acute triangle to include right triangles?

Michael Mendrin - 5 years, 1 month ago

@Michael Mendrin – Picking the four vertices of a square would give $s_4=4$ in this case. I think the combinatoric equation would be unchanged, so I leave it to you to calculate $s_{100}$ in this case...

Mark Hennings - 5 years, 1 month ago

@Mark Hennings – What bothered me about this problem is that it's not hard to see that the figure is 70% in the case of 5 points, but for 4 points it's 75%? And thereafter it's exactly 70%? Something seems off about this, which is why I'm looking at this more closely now. When I get around to it. It's tax time.

Michael Mendrin - 5 years, 1 month ago

@Michael Mendrin – The proportion $70$ % is an upper bound, and not a least upper bound. For that matter, the proportions $s_n \binom{n}{3}^{-1}$ are also upper bounds, and in general are not least upper bounds. either (according to the author of the MSE I referenced). I don't know whether anyone knows a sharp answer.

Mark Hennings - 5 years, 1 month ago

@Michael Mendrin – Putting $s_4=4$ gives $s_n = \binom{n}{3}$ for all $n \ge 4$ , so we have a very generous upper bound in the right-angle-triangles-included case!

Mark Hennings - 5 years, 1 month ago

@Mark Hennings – I agree that the ideal case of 7/10 acute triangles cannot hold over every set of 5 points, which is why this is merely an upper bound, and not the least upper bound.

I have updated the answer to 66.7

Calvin Lin Staff - 5 years, 1 month ago

@Calvin Lin – It's a tad irritating that I have now lost more points (-38) by having the answer I wanted to enter in the first place now marked as wrong than I gained (+16) by putting in the more standard one, particularly since I flagged the improved answer...

Mark Hennings - 5 years, 1 month ago

@Mark Hennings – Ah, sorry about that.

In this case, I have increased your Combinatorics ratings by +38, to reflect that you would have entered the answer of 66.7 originally. As this is a manual edit, you will not see this change till you answer another combinatorics question.

In future, if you got a decimal answer, but the question demands an integer answer, go ahead and round it off (either direction) and submit that answer. When we fix problems for integer -> decimal, we will mark the 2 closest integers as correct.

Calvin Lin Staff - 5 years, 1 month ago

@Calvin Lin – Thanks. I had spotted your correction.

It is useful to know how to record a "what it ought to be" solution!

Mark Hennings - 5 years, 1 month ago

Monte Carlo These Points!

The answer is 66.7.

1 solution

Moderator note:

0 pending reports