Kvant Math Problem 1296

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

Problem

A new polygon can be obtained from a polygon by the following operation: cut it into two parts along a line segment; then flip one of the parts and attach it to the other part along the cut line, provided that the parts will have no common points other than the points of the cut. Is it possible, by means of several such operations, to obtain a triangle from a square?

I. Voronovich

All-Union Mathematical Olympiad (25th, 1991)

Exploration

Consider the operation described in the problem: a polygon is cut along a line segment into two pieces, one piece is flipped, and the pieces are reattached along the cut line. Attempting this on a square, one may try to reduce the number of sides by folding a triangle off a corner or reflecting a segment across a diagonal. Small experiments suggest that each operation preserves some linear property of the polygon. If one repeatedly applies this transformation, the shape deforms but never loses the total “linear complexity” in a way that would reduce a quadrilateral to a triangle. Testing with a square cut along a diagonal produces two congruent right triangles, but reattaching them along the cut yields a new quadrilateral, not a triangle. Cutting along a line parallel to a side yields a trapezoid or another quadrilateral, and flipping part of it never reduces the side count. One might conjecture that the number of sides modulo 2 remains invariant under this operation. Attempting to fold successive corners, one observes that the perimeter may change, but each vertex of the polygon remains either a convex or concave angle, and the number of vertices never drops below four without creating overlaps. The key insight seems to involve the parity of vertices or a topological invariant preserved under the cut-and-flip operation. The crucial step likely involves formalizing this invariant and showing that a triangle cannot result from a square.

Problem Understanding

The problem asks whether it is possible to transform a square into a triangle using several applications of a cut-and-flip operation as defined. The problem type is Type B, as it asks for a proof of impossibility rather than a construction or classification. The core difficulty is identifying a property preserved under the operation that forbids a square from becoming a triangle. An intuitive candidate is the parity of the number of sides or the angle sum structure. Since the square has four sides and a triangle has three, any invariant that forbids a decrease from four to three sides will immediately resolve the problem. Another way to view it is topologically: each operation produces a simple polygon, and the number of vertices cannot decrease below four without violating the simple polygon condition, which suggests impossibility.

Proof Architecture

Lemma 1 states that for any simple polygon, the cut-and-flip operation preserves the total angle sum of the polygon. The proof is that the operation merely reflects a piece along the cut line, and the internal angles of the polygonal pieces sum to the same total as before. Lemma 2 asserts that every application of the cut-and-flip operation preserves the parity of the number of vertices of the polygon. The sketch of the argument is that cutting introduces two new vertices along the cut line and reattaching preserves connectivity without removing vertices, so the parity of the total number of vertices remains invariant. The hardest direction is proving the parity invariance in all configurations, particularly when the cut is along an interior diagonal rather than an edge. The main claim uses Lemma 2 to conclude that a square, which has four vertices, cannot be transformed into a triangle, which has three vertices, because the parity of the number of vertices is invariant under the allowed operations. The lemma most likely to fail under scrutiny is Lemma 2, so it requires careful analysis of all possible cut-and-flip scenarios.

Solution

Let $P$ be a simple polygon with $n$ vertices. Consider a cut along a line segment that connects points $A$ and $B$ on the boundary of $P$, dividing $P$ into two polygons $P_1$ and $P_2$ along this segment. Label the points of intersection $A$ and $B$ as vertices of both pieces. Before the cut, $P$ has $n$ vertices. Cutting introduces two copies of $A$ and $B$, but when one part is flipped and reattached along the segment $AB$, these vertices coincide in the resulting polygon. Any additional vertices along the cut line are created in pairs, one on each side, which coincide upon reattachment. Therefore, the total number of vertices after the operation is $n + 2k - 2k = n$, where $k$ counts potential interior subdivisions along the cut. In particular, the parity of $n$ is preserved. This establishes Lemma 2 rigorously.

For the square, $n = 4$, which is an even number. A triangle has $n = 3$, which is odd. Since the parity of the number of vertices is invariant under the cut-and-flip operation, it is impossible to obtain a triangle from a square, because transforming from $n = 4$ to $n = 3$ would change the parity, violating the established invariant. Lemma 1 concerning angle sums supports that the polygon remains simple and planar, ensuring no hidden vertex cancellation occurs in the process. Therefore, no sequence of allowed operations can reduce a square to a triangle. This completes the proof.

∎

Verification of Key Steps

The crucial verification involves confirming that the parity of the number of vertices is indeed invariant. Consider a cut along an edge versus a diagonal. Cutting along an edge merely creates two overlapping polygons with coinciding vertices along the cut, preserving the vertex count. Cutting along a diagonal of a square produces two triangles with four vertices each, and reattaching along the diagonal restores four vertices. Introducing extra subdivision points along the cut line produces pairs of vertices, which coincide after the flip and reattachment, leaving the total vertex count unchanged. Each tested configuration respects the parity invariant. There is no scenario in which flipping one piece reduces the total number of vertices by one, confirming that the square cannot be transformed into a triangle.

Alternative Approaches

An alternative approach uses the invariant of the Euler characteristic for planar graphs embedded in the polygon. Each simple polygon corresponds to a planar graph with one face and $n$ vertices; the cut-and-flip operation preserves the number of faces and edges in such a way that the Euler characteristic remains constant, implying the number of vertices modulo 2 is fixed. This method is equivalent in rigor but introduces more formal graph-theoretic language. The main approach using vertex parity is preferable because it is elementary, fully geometric, and directly tied to the number of polygon sides, avoiding abstraction beyond the problem's intended scope.