Maths Olympiad Prep

Library / /52 of 105

Combinatorics Difficulty 4.9 AIME Prove it United States

Problem:

One marks 16 points on a circle. What is the maximum number of acute triangles with vertices in these points?

Solution

Solution:

Consider the set of all angles M1M2M3M_{1} M_{2} M_{3}, where M1M_{1}, M2M_{2} and M3M_{3} is an arbitrary triple of selected points. There are 1615142=1680\frac{16 \cdot 15 \cdot 14}{2} = 1680 different angles in this set. Suppose nn of them are not acute. We shall prove n392n \geq 392.

For each integer mm between 1 and 7, take a chord with endpoints among the selected points such that there are exactly mm selected points to one side of the chord (not including the endpoints). We will call such a chord an mm-chord. Each mm-chord subtends not less than mm nonacute angles with vertices among the marked points. For each m6m \leq 6 there are exactly 1616 mm-chords, and for m=7m=7 there are exactly 88 of them. So the total number of nonacute angles is at least 16(1+2++6)+8×7=39216(1+2+\ldots+6) + 8 \times 7 = 392.

There are 1615146=560\frac{16 \cdot 15 \cdot 14}{6} = 560 triangles with vertices among the marked points. Each nonacute angle will "spoil" exactly one triangle, so the number of acute triangles is not greater than 560392=168560 - 392 = 168.

It is only left to construct an example with exactly 168 acute triangles. Mark eight consecutive vertices of a right 16-gon V1,,V8V_{1}, \ldots, V_{8}. Draw a line through the center of the 16-gon not parallel to V1V8V_{1} V_{8}, such that all VV's lie on the same side of that line (and not on the line). Reflecting the VV's with respect to that line we get points V1,,V8V_{1}' , \ldots, V_{8}'. We claim that the set V1,,V8,V1,,V8V_{1}, \ldots, V_{8}, V_{1}', \ldots, V_{8}' is as wanted. Indeed, there are no diametrically opposite points in this set (otherwise we would get V1V1=0V_{1} V_{1}' = 0 or V8V8=0V_{8} V_{8}' = 0), and so for m=7m=7 each mm-chord subtends exactly 8 nonacute angles. Moreover, for each m6m \leq 6 each mm-chord subtends exactly mm nonacute angles, and so n=392n=392, and the number of acute triangles is 168.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.