Maths Olympiad Prep

Library / /26 of 29

Geometry Difficulty 6.5 National Olympiad Prove it Croatia

Let n3n \ge 3 be an integer. Determine the minimum number of points one has to mark inside a convex nn-gon in order for the interior of any triangle with the vertices at vertices of the nn-gon to contain at least one of the marked points.

Solution

Since all diagonals from one vertex divide an nn-gon into n2n-2 disjoint triangles, at least n2n-2 points are necessary.

We claim that it is possible to mark n2n-2 points so that the given condition is satisfied. Denote the vertices of the given nn-gon with A1,A2,,AnA_1, A_2, \dots, A_n. Draw all the diagonals of the given nn-gon and color the areas bounded by the diagonals A1AkA_1A_k, AkAnA_kA_n and Ak1Ak+1A_{k-1}A_{k+1} for each k{2,3,,n1}k \in \{2, 3, \dots, n-1\}.
Figure 1

If we mark one point in each colored area then every triangle with vertices at vertices of the nn-gon will contain at least one of the marked points. Indeed, triangle AlAkAmA_lA_kA_m contains the whole colored area bounded by diagonals AlAkA_lA_k, AkAnA_kA_n and Ak1Ak+1A_{k-1}A_{k+1} for every 1l<k<mn1 \le l < k < m \le n. Hence, the triangle also contains the corresponding marked point.

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.