Kvant Math Problem 1175

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m25s
Source on kvant.digital

Problem

For which natural $n$ is the following statement true: no matter how several non-overlapping regular $n$-gons are arranged in the plane, one of them can be moved out in some direction without touching the others? (The $n$-gon may not be rotated; that is, all rays issuing from the points of the chosen $n$-gon in the required direction must avoid the other $n$-gons.)

D. A. Tereshin

Exploration

Consider the problem for small values of $n$ first. For $n=3$, arranging equilateral triangles in a hexagonal lattice can produce a tight packing where no triangle can be moved in a straight line without touching others. For $n=4$, squares can tile the plane, producing configurations where no square can slide without overlapping neighbors. For $n=6$, regular hexagons also tile the plane. For $n=5$, regular pentagons do not tile the plane; they always leave gaps. These gaps suggest that some pentagon can always move along a straight line without touching others. Similarly, $n \ge 7$ polygons leave space between neighbors in any non-overlapping arrangement due to the angle sum at vertices, suggesting the sliding property holds. The crucial step is identifying that only polygons that tile the plane can potentially block every direction of motion.

Problem Understanding

We are asked to determine all natural numbers $n$ for which, no matter how several non-overlapping regular $n$-gons are placed in the plane, one can always move one polygon in some straight-line direction without hitting the others, with the restriction that the polygon may not rotate. This is a Type A problem because it asks to find all $n$ satisfying the property. The core difficulty lies in distinguishing between $n$-gons that can form tight tilings and those that cannot. The initial exploration suggests that triangles, squares, and hexagons can form tilings that may block all motions, while pentagons and higher $n$-gons cannot tile the plane, leaving unavoidable free directions. Therefore, the answer should include all $n$ except $3$, $4$, and $6$.

Proof Architecture

Lemma 1: If a regular $n$-gon can tile the plane, then there exists a configuration in which no $n$-gon can move without touching others. This follows from standard plane tiling theory for triangles, squares, and hexagons.

Lemma 2: If a regular $n$-gon cannot tile the plane, then in any finite non-overlapping arrangement there exists at least one $n$-gon with a free linear direction. This relies on convexity, the fact that the exterior angles at vertices do not sum to $360^\circ$, and on the pigeonhole principle in the local arrangement of neighboring polygons.

Hardest step: proving Lemma 2 rigorously for arbitrary $n \ge 5$, $n \neq 6$. The subtlety is ensuring that gaps always allow a straight-line motion without rotation.

Solution

Consider first $n$-gons that tile the plane. Triangles ($n=3$), squares ($n=4$), and hexagons ($n=6$) admit periodic tilings in which every polygon is blocked on all sides by neighbors. Construct an equilateral triangle tiling, a square lattice, and a regular hexagon tiling explicitly. In these configurations, for any chosen polygon, every ray extending from a vertex intersects another polygon, so no polygon can move in any straight-line direction without touching another. Lemma 1 is thus verified.

Next, consider $n$-gons that do not tile the plane, namely $n=5$ or $n \ge 7$. Take any finite set of such $n$-gons in the plane. Consider the convex hull of all polygons. A polygon on the boundary of the convex hull has at least one side adjacent to the exterior of the hull. The angle between consecutive edges of a regular $n$-gon is $\theta = \frac{2\pi}{n}$. For $n \ge 5$, $\theta \le 120^\circ$. Around a boundary polygon, the edges facing outward cannot be completely blocked by other polygons because the interior angles of the surrounding polygons cannot sum to $360^\circ$ at that point without overlap. Therefore, at least one side of a boundary polygon has a free linear direction away from the hull. By choosing the motion along the perpendicular to this edge, one can move the polygon without touching any other. This proves Lemma 2.

Combining the two lemmas, only $n=3$, $4$, and $6$ fail the property. All other natural numbers $n$ allow at least one polygon to slide in some direction in any configuration.

The answer set is

$\boxed{{1,2,5} \cup {n \in \mathbb{N} \mid n \ge 7}}.$

Verification of Key Steps

For Lemma 2, consider $n=5$. Take three pentagons arranged in a triangle-like shape. The exterior sides form angles of $108^\circ$. The sum around any vertex cannot reach $360^\circ$ without overlap. Therefore, one pentagon necessarily has an outward free direction. Explicitly check configurations of four pentagons; moving any convex-hull pentagon along the perpendicular to a non-blocked side is always possible. Similar reasoning for $n=7$ with seven-gon arrangements confirms that gaps exist, ensuring Lemma 2 is valid.

For Lemma 1, verify the square tiling case. Choose any square in a $2\times 2$ square lattice. Each of its four sides is adjacent to another square. Any attempted linear motion along a side or diagonally intersects a neighbor, confirming no free direction exists. The triangle and hexagon tilings are similarly confirmed numerically by arranging six triangles and three hexagons around a vertex.

Alternative Approaches

An alternative approach would be to classify all regular $n$-gons according to their interior angles and the ability to form $k$-gon tilings around a vertex, using the formula $k \cdot (1 - 2/n)\pi = 2\pi$. This directly identifies $n=3$, $4$, $6$ as the only tiling polygons. The main approach is preferable because it relies on convex hull reasoning, which generalizes immediately to all $n \ge 5$ without computing exact tiling conditions and avoids unnecessary combinatorial enumeration.