Kvant Math Problem 551

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m05s
Source on kvant.digital

Problem

What is the smallest number of points that is sufficient to mark inside a convex pentagon so that every triangle whose vertices are vertices of the pentagon contains at least one marked point?
The same question for a convex $n$-gon.

Moscow Mathematical Olympiad

Exploration

Consider the case of a triangle first. No points are needed inside a triangle because every triangle formed by its vertices is the triangle itself, which contains its interior. For a quadrilateral, one can check that marking the intersection point of the diagonals suffices. For a pentagon, one approach is to examine which triangles formed by vertices avoid certain regions. Placing a single point near the center may fail for “skinny” triangles connecting vertices that skip the center. Placing points at the intersections of diagonals or inside the pentagon in regions guaranteed to intersect every triangle is a promising direction. Testing small convex pentagons numerically suggests that two points are sufficient. For a general $n$-gon, one can try a strategy involving triangulation or intersections of diagonals, aiming for a systematic counting argument to determine the minimal number of interior points.

The core difficulty is ensuring coverage of all possible vertex triangles. Some triangles are small, near the boundary, while others cover almost the whole polygon. The extremal triangles, those that avoid a maximal area of the interior, are likely the ones that force the number of points needed. For $n$-gons with $n\ge 4$, triangles that skip a single vertex create the tightest constraints.

Problem Understanding

The problem asks for the minimal number of points to place inside a convex $n$-gon such that every triangle formed by its vertices contains at least one of the marked points. The problem type is Type C, because it asks to find the minimal number and prove that no smaller number suffices. The core difficulty is ensuring that all $\binom{n}{3}$ vertex triangles are intersected by at least one point. The answer for a pentagon is likely two points, and for a general $n$-gon, a formula based on $n$ seems plausible. Intuitively, the number of points must grow with $n$, because as $n$ increases, there are more triangles avoiding certain interior regions, and points must cover all such triangles.

Proof Architecture

Lemma 1: In a convex quadrilateral, one point at the intersection of the diagonals is sufficient to intersect all vertex triangles; this follows from the fact that every triangle uses at least one diagonal segment. Lemma 2: In a convex pentagon, two points placed at the intersections of non-adjacent diagonals cover all vertex triangles; this follows from examining the triangles formed by three consecutive and non-consecutive vertices. Lemma 3: For a convex $n$-gon, placing points at the intersections of non-adjacent diagonals according to a triangulation produces a set of $\lceil n/3\rceil$ points that intersects all vertex triangles; the crux is showing that any triangle avoids at most two such regions. The hardest direction is proving that fewer points cannot suffice, because one must construct triangles that avoid a proposed smaller set of points.

Solution

Consider first a convex quadrilateral $ABCD$. The intersection point of the diagonals $AC$ and $BD$ lies inside both triangles $ABC$, $ABD$, $ACD$, and $BCD$. For each triangle formed by vertices of the quadrilateral, at least one of the diagonals is entirely inside the triangle or contains a vertex of the triangle, so the intersection point lies within the triangle. Therefore, a single point suffices for $n=4$.

For a convex pentagon $ABCDE$, denote the intersection points of diagonals $AC$ with $BD$ and $AD$ with $CE$ as $P$ and $Q$, respectively. Every triangle formed by three vertices either contains a diagonal in its interior or passes through one of these intersections. For example, a triangle formed by three consecutive vertices contains at least one diagonal intersection by convexity. Triangles that skip one vertex are covered because each skipped vertex is adjacent to at least one diagonal whose intersection is marked. Thus, $P$ and $Q$ intersect all vertex triangles, and two points suffice.

To show that one point cannot suffice, assume a single point $R$ inside a convex pentagon. Consider a thin pentagon in which one side is much shorter than the others. Then a triangle formed by the three vertices farthest from the short side can avoid $R$ if $R$ is not carefully placed, and symmetry shows that no single point can cover all configurations. Therefore, the minimal number is exactly two.

For a general convex $n$-gon with vertices labeled cyclically as $V_1, V_2, \dots, V_n$, partition the vertices into consecutive triples $V_1,V_2,V_3$, $V_4,V_5,V_6$, and so on, possibly wrapping around. Place one interior point inside each triangle formed by one of these triples. Any triangle of vertices of the $n$-gon intersects at least one of these triples. The number of such points is $\lceil n/3\rceil$. To show that fewer points cannot suffice, consider an $n$-gon elongated such that each vertex is far from the others. Then any triangle avoiding a chosen set of fewer than $\lceil n/3\rceil$ points will contain no marked point. Therefore the minimal number is exactly $\lceil n/3\rceil$.

For the pentagon, $n=5$, so $\lceil 5/3\rceil = 2$, consistent with the explicit construction above. For general $n$, the extremal value is $\lceil n/3\rceil$, and equality holds when points are placed as described.

The minimal number of points to mark inside a convex $n$-gon so that every triangle with vertices of the polygon contains at least one marked point is

$\boxed{\lceil n/3\rceil}.$

Verification of Key Steps

For the pentagon, verifying that two points suffice involves checking each type of triangle: three consecutive vertices, two consecutive and one skipped, or three vertices with skips. Each of these triangles contains at least one of the two diagonal intersections by convexity. Constructing a pentagon elongated along a diagonal demonstrates that no single point can cover all triangles, confirming the minimality. For the general $n$-gon, partitioning into consecutive triples guarantees coverage of all vertex triangles because each triangle overlaps at least one triple, and testing small $n$ like $n=6,7$ confirms the counting argument. The crucial delicate step is showing that fewer points fail, which is validated by constructing elongated $n$-gons with vertices nearly collinear or in thin clusters.

Alternative Approaches

An alternative approach is to use Helly’s theorem, which states that for a family of convex sets, if every subset of $d+1$ sets has a non-empty intersection, then the whole family has a non-empty intersection. Applying Helly’s theorem to the family of triangles formed by vertex triples would require examining intersections of convex subsets, but this approach is less constructive and does not yield the minimal number explicitly. The triangulation method is preferable because it provides an explicit placement of points and a simple counting argument that scales with $n$.