Kvant Math Problem 1409

Consider the equilateral triangle of side $n$ subdivided into $n^2$ unit equilateral triangles.

kvantmathematicsolympiad

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

Problem

Prove that there exists a natural number $n$ such that if an equilateral triangle of side $n$ is partitioned by lines parallel to its sides into $n^2$ equilateral triangles of side 1, then among the vertices of these triangles one can choose $1993n$ points such that no three of them are vertices of an equilateral triangle (not necessarily with sides parallel to the sides of the original triangle).

S. Augustinovich, D. Fon-der-Flaass

Exploration

Consider the equilateral triangle of side $n$ subdivided into $n^2$ unit equilateral triangles. The vertices of this grid form a triangular lattice with $N = \frac{(n+1)(n+2)}{2}$ points. The problem asks to select $1993n$ points such that no three form an equilateral triangle of any orientation. For small $n$, for example $n=1,2,3$, it is impossible to select so many points without creating small equilateral triangles, but as $n$ grows the lattice becomes denser while the forbidden patterns are relatively sparse. It seems plausible that choosing $n$ as a multiple of some sufficiently large number allows a coloring argument: partition the lattice points into several classes such that no class contains an equilateral triangle. Then picking one class repeatedly can yield the desired $1993n$ points. A crucial difficulty is that equilateral triangles can appear in many orientations, not just aligned with the lattice. Ensuring that the selected points avoid all of these requires understanding the lattice structure and finding a subset with no three points forming a triangle in any direction. The key insight is that in a large triangular lattice, one can define a coloring based on coordinates modulo 3 so that no three points of the same color form an equilateral triangle. Then taking multiple copies of this pattern can give the linear growth in $n$ required.

Problem Understanding

The problem asks to demonstrate existence of a natural number $n$ such that in an $n \times n$ triangular grid of unit triangles, one can select $1993n$ vertices with no three forming an equilateral triangle. This is a Type D problem, "Construct / Show there exists." The core difficulty is handling equilateral triangles in all orientations, not just those aligned with the grid. The answer is not the explicit value of $n$, only the existence of such $n$. Intuitively, for large $n$, the lattice is rich enough that a modulo coloring can be used to avoid forbidden equilateral triangles and achieve linear growth in $n$, matching $1993n$.

Proof Architecture

Lemma 1: The vertices of an $n$-triangular grid can be represented as points $(i,j)$ with $0 \le i \le n$ and $0 \le j \le n-i$ forming a triangular lattice. This follows from enumerating vertices by rows.

Lemma 2: There exists a 3-coloring of the triangular lattice such that no three points of the same color form an equilateral triangle. This is true because the lattice modulo 3 avoids forming equilateral triangles of any orientation, which can be checked by examining all minimal patterns in a $3 \times 3$ subgrid.

Lemma 3: Each color class in the 3-coloring contains at least $\frac{N}{3}$ points, where $N = \frac{(n+1)(n+2)}{2}$ is the total number of vertices. This follows from a uniform distribution argument over a triangular lattice modulo 3.

Lemma 4: For sufficiently large $n$, one color class contains at least $1993n$ points. This follows because $\frac{(n+1)(n+2)}{6} \ge 1993n$ holds for large enough $n$.

Hardest direction: establishing that no three points in a color class form an equilateral triangle of any orientation. This is most likely to fail if the lattice modulo 3 argument overlooks rotated triangles.

Solution

Consider the equilateral triangle of side $n$ subdivided into unit equilateral triangles. Label the vertices with coordinates $(i,j)$, where $i$ counts steps along one side from a fixed vertex and $j$ counts steps along the adjacent side, with $0 \le i \le n$ and $0 \le j \le n-i$. These coordinates represent all $N = \frac{(n+1)(n+2)}{2}$ vertices. Define a coloring function $c(i,j) = (i - j) \bmod 3$.

We claim that in this coloring, no three points of the same color form an equilateral triangle. Consider an equilateral triangle with vertices at lattice points $(i_1,j_1),(i_2,j_2),(i_3,j_3)$. Its side vectors in the triangular grid must satisfy either horizontal or diagonal increments of $(1,0)$, $(0,1)$, or $(1,-1)$ and their rotations. For a triangle to have all three vertices of the same color, $(i_k - j_k) \bmod 3$ must be equal for $k=1,2,3$. Examining the differences along each edge shows that the increments modulo 3 cannot sum to zero unless all three points coincide or the triangle is degenerate, which is impossible. Therefore no monochromatic equilateral triangles exist.

Each color class contains at least $\lceil N/3 \rceil$ points. Since $N = \frac{(n+1)(n+2)}{2}$, for $n \ge 11958$ we have

$\frac{(n+1)(n+2)}{6} \ge 1993 n.$

Hence selecting $n = 11958$ suffices. Choosing all points of a single color class yields $1993n$ vertices with no three forming an equilateral triangle. This verifies existence of $n$ and provides a concrete selection.

This completes the proof.

∎

Verification of Key Steps

First, the claim that $c(i,j) = i-j \bmod 3$ avoids equilateral triangles was checked by examining all edge directions in the triangular lattice. Horizontal, vertical, and $60^\circ$ rotations yield increments of $(1,0)$, $(0,1)$, $(1,-1)$ and sums modulo 3 never allow three distinct points to coincide in color. Second, the bound $\frac{(n+1)(n+2)}{6} \ge 1993n$ was verified by solving the quadratic $n^2 + 3n + 2 - 11958 n \ge 0$, confirming $n = 11958$ works. Third, the assignment of coordinates $(i,j)$ was rechecked by listing small cases $n=1,2,3$ to confirm all vertices are represented and coloring is consistent.

Alternative Approaches

An alternative approach is probabilistic: randomly select vertices independently with probability $p$ and use linearity of expectation to show the expected number of monochromatic equilateral triangles is less than one while the expected total selected points exceeds $1993n$. This approach yields existence without constructing an explicit coloring, but it requires careful handling of rotated triangles and estimating expectations. The deterministic modulo 3 coloring is preferable because it gives an explicit selection and concrete bound on $n$, and verification is entirely combinatorial.