Let be an integer. Determine the minimum number of points one has to mark inside a convex -gon in order for the interior of any triangle with the vertices at vertices of the -gon to contain at least one of the marked points.
Solution
Since all diagonals from one vertex divide an -gon into disjoint triangles, at least points are necessary.
We claim that it is possible to mark points so that the given condition is satisfied. Denote the vertices of the given -gon with . Draw all the diagonals of the given -gon and color the areas bounded by the diagonals , and for each .
If we mark one point in each colored area then every triangle with vertices at vertices of the -gon will contain at least one of the marked points. Indeed, triangle contains the whole colored area bounded by diagonals , and for every . 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.