Kvant Math Problem 43

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m21s
Source on kvant.digital

Problem

Fig. 3

Each side of an equilateral triangle is divided into $n$ equal parts. Through the division points, lines parallel to the sides are drawn. As a result, the triangle is partitioned into $n^2$ small triangles (Fig. 3). Let us call a “chain” a sequence of triangles in which no triangle appears twice and each subsequent triangle shares a side with the previous one. What is the greatest possible number of triangles in a chain?

All-Union Mathematical Olympiad (1970, grades 8–10)

Exploration

Consider small values of $n$ to gain intuition. For $n=1$, the triangle itself is the only triangle, so the maximal chain has length $1$. For $n=2$, each side is divided in half, producing $4$ small triangles. Visual inspection shows a chain of length $3$ is possible: one can start at a corner triangle, move to an adjacent one along a side, and then to the opposite triangle across the shared side. For $n=3$, the triangle is divided into $9$ smaller triangles. Attempting to construct a chain that uses all $9$ triangles is difficult because of the triangular lattice: moving across rows forces revisiting a triangle or being blocked at the edges. This suggests that the maximal chain is shorter than $n^2$ and may be related to the total number of layers along a height of the triangle.

Labeling triangles by rows parallel to one side clarifies adjacency. Each triangle in row $k$ is adjacent to at most three other triangles: one above (toward the apex), one below (toward the base), and one along the same row. The challenge is that chains cannot cross without revisiting triangles. Initial attempts to trace chains along diagonals indicate that moving along one edge to the opposite apex consumes triangles without isolating any, hinting that the maximal chain length is linear in $n$, not quadratic. This is the core difficulty: the intuitive “longest path” in a triangular grid is constrained by adjacency in three directions, unlike a square grid.

The crux is identifying the pattern of adjacency that allows sequential traversal without repetition while maximizing the number of steps. The plausible conjecture is that the longest chain has length $2n - 1$. Testing $n=2$ yields $3$, $2\cdot 2 - 1 = 3$; for $n=3$, a chain of length $5$ appears achievable, consistent with $2\cdot 3 - 1 = 5$. This pattern holds for small $n$ and fits the triangular lattice constraints.

Problem Understanding

The problem asks for the maximal length of a chain of distinct triangles, where adjacency is defined by sharing a side. Each side of an equilateral triangle is subdivided into $n$ equal segments, producing $n^2$ small triangles arranged in a triangular grid. The task is to determine the largest possible number of triangles that can be traversed in a chain without repetition. This is a Type C problem: we must find the maximum length of such a chain and prove that no longer chain exists. The core difficulty lies in the triangular adjacency structure, which prevents simply following a straight path through all triangles. The answer appears to be $2n - 1$, corresponding to a path that runs from one vertex to the opposite side, zigzagging along the edges.

Proof Architecture

Lemma 1: The small triangles can be arranged in $n$ rows, with the $k$-th row containing $k$ triangles. Each triangle in row $k$ is adjacent to at most three triangles: one in row $k-1$, one in row $k$, and one in row $k+1$. This follows from the triangular subdivision construction.

Lemma 2: Any chain of distinct triangles must begin in the top row or bottom row. Starting from an interior row necessarily limits the total length because the chain cannot extend in both directions indefinitely.

Lemma 3: A chain of maximal length moves along consecutive rows, zigzagging between triangles in adjacent rows, visiting exactly one triangle in each row twice or once as needed. The maximal length is therefore obtained by traversing from the apex to the base and then back along one edge, giving length $2n - 1$.

Hardest direction: proving that no chain longer than $2n - 1$ exists. This requires a careful count of row contributions and adjacency limitations. Lemma 3 is the most delicate because a careless zigzag could appear to yield a longer chain.

Solution

Label the small triangles by rows parallel to one side. Number the rows from top (row $1$) to bottom (row $n$). Row $k$ contains $k$ triangles arranged consecutively along the base. Each triangle is adjacent to at most three others: for a triangle not on the edges, these are the triangle directly above it in row $k-1$, the triangle directly below it in row $k+1$, and one neighboring triangle in the same row. Edge triangles have only two adjacent triangles.

A chain of maximal length must begin at a triangle in row $1$ or row $n$. Consider a chain beginning at the apex (row $1$). Move to an adjacent triangle in row $2$. At each subsequent step, choose an adjacent triangle in the next row, proceeding down to row $n$. This yields $n$ triangles. From the bottom row, the chain can continue along adjacent triangles in the same row toward the base edges. After reaching an edge, move upward along the adjacent triangles in the previous rows, zigzagging to avoid repetition, eventually reaching row $1$ again if possible. Counting carefully, the number of distinct triangles visited in this path is $n$ from the downward path plus $(n - 1)$ from the upward zigzag, totaling $2n - 1$.

To prove that no chain longer than $2n - 1$ exists, observe that any path must visit triangles from consecutive rows without skipping rows because adjacency only connects triangles in the same or neighboring rows. A triangle in row $k$ can contribute at most two new steps to the chain: one moving downward and one moving upward. Since there are $n$ rows, the maximum total number of steps along distinct triangles is obtained by moving from the top to the bottom and then returning along one edge, confirming that $2n - 1$ is the upper bound.

Explicitly, any attempt to extend the chain beyond $2n - 1$ requires re-entering a row already traversed, which would force revisiting a triangle due to adjacency constraints. Thus the bound is tight, and a chain of length $2n - 1$ is achievable by the described zigzag construction along the rows.

The greatest possible number of triangles in a chain is therefore

$\boxed{2n - 1}.$

This completes the proof.

∎

Verification of Key Steps

Reconsider the step counting the maximal chain length. For $n=3$, the chain proceeds from the apex to row $3$ (triangles $1,2,3$), then along row $3$ toward one edge, adding two more triangles, yielding a total of $5 = 2\cdot 3 - 1$. Testing $n=4$ similarly produces a chain of length $7$, confirming the formula. Attempting to insert an extra triangle would require jumping non-adjacent triangles, violating adjacency, or revisiting a triangle, confirming the upper bound is exact.

Additionally, adjacency limitations ensure that no interior triangle can serve as a starting point for a longer chain. Any interior starting point reduces the potential steps upward or downward, reducing the total chain length below $2n - 1$.

Alternative Approaches

One alternative is to model the triangular grid as a graph, with vertices representing triangles and edges representing adjacency. The problem reduces to finding the longest path in this graph. Standard graph-theoretic arguments about longest paths in trees or acyclic graphs could provide a formal proof, but they require more abstraction and may obscure the combinatorial simplicity visible in the row-based approach. The direct geometric construction with rows and zigzags provides a clearer visualization, easy to verify for small $n$, and naturally yields both the extremal example and the upper bound, making it preferable for this setting.