2
$\begingroup$

I encounter the following problem with solution. But I do not quite understand the argument for 5, 10 points and eventually 100 points. Can someone elucidate the details?


Problem

In a plane there are $100$ points, no three of which are collinear. Consider all possible triangles having these point as vertices. Prove that no more than $70$% of these triangles are acute-angled.

Solution

At most $3$ of the triangles formed by $4$ points can be acute. It follows that at most $7$ out of the $10$ triangles formed by any $5$ points can be acute. For given $10$ points, the maximum no. of acute triangles is: the no. of subsets of $4$ points $\times3/$the no. of subsets of $4$ points containing $3$ given points. The total no. of triangles is the same expression with the first $3$ replaced by $4$. Hence at most $\frac34$ of the $10$, or $7.5$, can be acute, and hence at most $7$ can be acute. The same argument now extends the result to $100$ points. The maximum number of acute triangles formed by $100$ points is: the no. of subsets of $5$ points $\times7$/the no. of subsets of 5 points containing $3$ given points. The total no. of triangles is the same expression with $7$ replaced by $10$. Hence at most $\frac7{10}$ of the triangles are acute.

$\endgroup$
4
$\begingroup$

First, show that out of 4 points, at most 3 triangles are acute.

Out of 5 points, there are ${ 5 \choose 4 } =5$ sets of 4 points. In each of these sets, there are at most 3 triangles that are acute. This gives us $5 \times 3 = 15 $ acute triangles, but we double counted.
Notice that each triangle is counted exactly twice. Hence, there are at most $ \lfloor \frac{15}{2} \rfloor = 7$ acute triangles.

Now do the same, bootstrapping your way up to 10 points.

$\endgroup$
  • $\begingroup$ Thank you. My follow-up question is, how does one pick the bootstrapping sequence, e.g., in this case 4,5,100? Trial and error? $\endgroup$ – Hans Apr 11 '14 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.