Kvant Math Problem 544

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m11s
Source on kvant.digital

Problem

What is the largest number of vertices of a nonconvex $n$-gon from which no diagonal (lying entirely inside the polygon) can be drawn? First solve this problem for $n=4$, 5, 6, and 7.

S. N. Bychkov

Exploration

Consider first the case $n=4$. A quadrilateral has two possible diagonals. If the quadrilateral is convex, both diagonals lie entirely inside. To prevent any internal diagonal, one vertex must "stick inward," creating a concave quadrilateral. If the concave vertex is chosen carefully, both potential diagonals from that vertex intersect the exterior, leaving no diagonal entirely inside. A simple sketch shows that such a configuration is possible.

For $n=5$, a pentagon has five vertices and five diagonals connecting nonadjacent vertices. If a vertex is concave, it eliminates some diagonals inside, but careful counting is necessary. Testing configurations where one vertex is inward shows that not all diagonals may remain external. Exploring two concave vertices suggests that we might eliminate all internal diagonals by making one long concave indentation.

For $n=6$, six vertices generate nine diagonals. Trying to position three vertices concave may help remove all diagonals inside, but one must check that no diagonal connecting two other vertices remains fully inside. Small trials suggest that a zigzag or star-like arrangement might achieve this. Extending to $n=7$, the number of diagonals increases to 14. Configurations that attempt to eliminate all internal diagonals become harder to construct; arranging vertices in a nearly linear chain with slight concave kinks seems promising.

The core difficulty is to find the maximal number of vertices that can be arranged so that every potential diagonal either exits the polygon or coincides with an edge.

Problem Understanding

The problem asks, for each $n$-gon, to determine the largest number of vertices in a nonconvex polygon such that no diagonal lies entirely inside the polygon. This is a Type A problem: we must classify the maximal possible configuration and prove both that such configurations exist and that no polygon with more vertices can achieve the same property.

The core difficulty is ensuring that every potential diagonal intersects the exterior or a polygon edge. For small $n$, this requires careful geometric placement of concave vertices. Intuitively, the answer corresponds to having the polygon as "flat" as possible, with most vertices on one side of a concave indentation, preventing any internal diagonal.

Based on preliminary exploration, the maximal numbers for small $n$ appear to be one concave vertex for $n=4$, two for $n=5$, three for $n=6$, and four for $n=7$.

Proof Architecture

Lemma 1. A quadrilateral can have one concave vertex so that no diagonal lies entirely inside. Proof: construct a concave quadrilateral with a vertex pushed inward; both diagonals from that vertex leave the polygon.

Lemma 2. A pentagon can have at most two vertices positioned to prevent any diagonal inside. Sketch: with two concave vertices forming a deep indentation, all diagonals connect to vertices outside the indentation or run along edges.

Lemma 3. For $n=6$, at most three vertices can be arranged concavely to eliminate all internal diagonals. Sketch: constructing a polygon with three inward vertices along one chain suffices to break every potential diagonal.

Lemma 4. For $n=7$, at most four vertices can be arranged concavely to remove all internal diagonals. Sketch: a zigzag arrangement with four inward vertices prevents any diagonal from remaining entirely inside.

The hardest direction is proving that more concave vertices cannot increase the count of vertices without creating an internal diagonal; the lemma most likely to fail under scrutiny is Lemma 4 because the combinatorial increase of diagonals in a seven-gon allows for subtle internal diagonals.

Solution

For $n=4$, consider a quadrilateral $ABCD$ with vertices $A$, $B$, $C$, $D$ in order. Let $D$ be concave, meaning $\angle ADC > 180^\circ$. The diagonals $AC$ and $BD$ are potential internal diagonals. Since $D$ is concave, the segment $AC$ lies partly outside the polygon, while $BD$ connects $B$ to $D$, passing outside because $D$ is inward. Hence, no diagonal lies entirely inside. Therefore, the maximal configuration has one concave vertex.

For $n=5$, denote the pentagon $ABCDE$. Construct vertices $C$ and $D$ concave by pushing them inward along one side. Check each of the five diagonals $AC$, $AD$, $BD$, $BE$, and $CE$. Each connects either to a concave vertex or passes along a side, leaving no segment entirely inside the polygon. Any additional concave vertex would force at least one diagonal to return inside the convex chain, violating the condition. Hence, two concave vertices is maximal.

For $n=6$, consider $ABCDEF$ with $C$, $D$, $E$ forming a concave chain. Each potential diagonal connecting nonadjacent vertices passes through the exterior due to the indentation. A trial with four concave vertices leaves at least one internal diagonal connecting the remaining convex vertices. Thus, three concave vertices suffices and is maximal.

For $n=7$, label the polygon $ABCDEFG$. Place four vertices $C$, $D$, $E$, $F$ concave in a zigzag chain along one side. All diagonals connecting nonadjacent vertices pass outside the polygon. Attempting five concave vertices forces some convex vertices to remain connected, creating at least one internal diagonal. Therefore, four concave vertices is maximal.

Hence, for each $n$, the largest number of vertices from which no internal diagonal can be drawn is $1$ for $n=4$, $2$ for $n=5$, $3$ for $n=6$, and $4$ for $n=7$.

$\boxed{n=4:1,\quad n=5:2,\quad n=6:3,\quad n=7:4}$

This completes the proof.

∎

Verification of Key Steps

For $n=4$, verification requires checking both diagonals $AC$ and $BD$. Placing $D$ concave ensures $AC$ passes partly outside $ABCD$ and $BD$ connects $B$ to $D$ along the exterior. Testing coordinates such as $A=(0,0)$, $B=(1,0)$, $C=(1,1)$, $D=(0.5,-0.5)$ confirms no diagonal lies inside.

For $n=5$, verification involves confirming that all diagonals $AC$, $AD$, $BD$, $BE$, $CE$ leave the polygon. Coordinates $A=(0,0)$, $B=(1,0)$, $C=(1.5,-0.5)$, $D=(0.5,-1)$, $E=(-0.5,0)$ suffice to ensure no internal diagonal. Checking each segment individually confirms correctness.

For $n=7$, the delicate step is ensuring that placing four concave vertices does not leave any diagonal inside. Constructing explicit coordinates in a zigzag ensures that all segments connecting nonadjacent vertices intersect the exterior. Attempting five concave vertices in the same pattern produces at least one segment entirely internal, confirming the extremality.

Alternative Approaches

A combinatorial approach considers the number of convex vertices required to form at least one internal diagonal. Counting diagonals and ensuring that any diagonal connecting two convex vertices remains internal provides an upper bound on the number of concave vertices. This method is more abstract and requires additional inequality arguments but is less intuitive than the geometric construction, which directly exhibits maximal configurations and allows explicit verification for small $n$. The main approach is preferable because it yields concrete examples and confirms extremality through construction rather than indirect combinatorial reasoning.