Kvant Math Problem 944
The figure is the regular hexagon of side length $2$ subdivided into $24$ congruent equilateral triangles.
Verified: yes
Verdicts: PASS + PASS
Solve time: 11m35s
Source on kvant.digital
Problem
A regular hexagon is divided into 24 congruent triangles, as shown in Figure 2. Distinct numbers are written at all 19 vertices of the resulting figure. Prove that among the 24 triangles of the partition there are at least 7 whose vertex numbers are arranged in increasing order when read counterclockwise.
Figure 2
A. A. Berzinsh
All-Union Mathematical Olympiad (1985)
Exploration
The figure is the regular hexagon of side length $2$ subdivided into $24$ congruent equilateral triangles. The resulting triangular lattice has $19$ vertices.
A natural way to use the distinct numbers is to orient every edge from the smaller endpoint to the larger endpoint. Then each small triangle receives a local orientation pattern.
For a triangle whose vertices, read counterclockwise, carry numbers $a,b,c$, the desired triangles are exactly those for which $a<b<c$ after a cyclic choice of the starting vertex. Equivalently, if the vertices are listed counterclockwise, the order of their labels is a cyclic permutation of $(1,2,3)$.
For a fixed triangle, compare the orientation of each edge with the counterclockwise traversal of the boundary of that triangle. A computation with the six possible orders of three distinct labels shows that for a desired triangle, two boundary edges agree with the counterclockwise traversal and one disagrees, while for any other triangle the situation is reversed. Hence the quantity
$$(\text{agreeing edges})-(\text{disagreeing edges})$$
equals $+1$ for a desired triangle and $-1$ for every other triangle.
Summing this quantity over all $24$ triangles suggests a telescoping phenomenon. Every interior edge belongs to two triangles and is traversed in opposite directions in their counterclockwise boundary walks, so its contributions cancel. Only boundary edges survive.
The crucial point is then to estimate the contribution of the $12$ boundary edges. Along the boundary cycle, an edge contributes $+1$ precisely when the numbers increase in the counterclockwise direction and $-1$ otherwise. Since the boundary labels are distinct, the cycle cannot consist entirely of decreases; there is at least one increase. Thus among the $12$ boundary edges there are at most $11$ decreases, giving a total boundary contribution at least
$$1-11=-10.$$
This already yields the target bound.
Problem Understanding
We must prove that no matter how $19$ distinct numbers are placed at the vertices of the triangular lattice inside the regular hexagon, at least $7$ of the $24$ small triangles have their vertex labels in increasing order when read counterclockwise.
This is a Type B problem.
The core difficulty is to convert a local condition on each triangle into a global quantity that can be summed over the whole triangulation. The cancellation of contributions along interior edges is the central idea.
Proof Architecture
Define an orientation on every edge from the smaller endpoint to the larger endpoint.
For each small triangle $T$, define $s(T)$ as the number of boundary edges whose orientation agrees with the counterclockwise traversal of $T$ minus the number of boundary edges whose orientation disagrees; then $s(T)=1$ for a desired triangle and $s(T)=-1$ otherwise, because a direct check of the six label orders gives exactly these values.
When $\sum s(T)$ is taken over all $24$ triangles, every interior edge contributes $0$, because the two adjacent triangles traverse that edge in opposite directions.
Hence $\sum s(T)$ equals the contribution of the $12$ boundary edges of the hexagon.
If $A$ and $D$ denote the numbers of boundary edges along which the labels increase and decrease, respectively, in the counterclockwise direction, then $A+D=12$ and $A\ge1$, since a cyclic sequence of distinct numbers cannot decrease at every step.
Therefore the boundary contribution is $A-D\ge1-11=-10$.
If $P$ is the number of desired triangles and $N$ the number of the remaining triangles, then $P+N=24$ and $P-N=\sum s(T)\ge-10$, which implies $P\ge7$.
The lemma most likely to fail under scrutiny is the first one, namely the verification that $s(T)$ equals $+1$ or $-1$ according to the orientation type of the triangle.
Solution
Orient every edge of the triangulation from the smaller endpoint to the larger endpoint.
For a small triangle $T$, traverse its boundary counterclockwise. Let
$$s(T)=#{\text{boundary edges of }T\text{ whose orientation agrees with the traversal}}$$
$$-#{\text{boundary edges of }T\text{ whose orientation disagrees with the traversal}}.$$
Since the three vertex labels of $T$ are distinct, there are six possible orders of these labels around the triangle.
If the labels are in increasing order when read counterclockwise, then after naming the vertices counterclockwise as $1,2,3$, the edge orientations are
$$1\to2,\qquad 2\to3,\qquad 1\to3.$$
Along the counterclockwise boundary, the first two edges agree with the traversal and the third disagrees. Hence
$$s(T)=2-1=1.$$
For any of the other three cyclic orders, the same calculation gives one agreeing edge and two disagreeing edges, so
$$s(T)=1-2=-1.$$
Thus
$$s(T)= \begin{cases} 1,&\text{if }T\text{ is increasing counterclockwise},\ -1,&\text{otherwise}. \end{cases}$$
Let $P$ be the number of increasing counterclockwise triangles and $N$ the number of the others. Then
$$P+N=24$$
and
$$\sum_T s(T)=P-N.$$
Now sum $s(T)$ over all $24$ triangles.
Every interior edge belongs to exactly two triangles. In the counterclockwise boundary traversal of those two triangles, that edge is traversed in opposite directions. Since the orientation of the edge itself is fixed, its contribution to one triangle is the negative of its contribution to the other. Hence all interior-edge contributions cancel.
Therefore
$$\sum_T s(T)$$
is equal to the total contribution of the $12$ boundary edges of the hexagon.
Let $A$ be the number of boundary edges along which the labels increase when the boundary is traversed counterclockwise, and let $D$ be the number of boundary edges along which they decrease. Then
$$A+D=12,$$
and the boundary contribution equals
$$A-D.$$
The boundary vertices carry distinct numbers. If every boundary edge were decreasing in the counterclockwise direction, then after going once around the boundary we would obtain a strictly decreasing cycle of numbers, which is impossible. Hence
$$A\ge1.$$
Consequently,
$$A-D=A-(12-A)=2A-12\ge2\cdot1-12=-10.$$
Thus
$$P-N=\sum_T s(T)\ge-10.$$
Together with $P+N=24$, this gives
$$2P=(P+N)+(P-N)\ge24-10=14.$$
Hence
$$P\ge7.$$
So among the $24$ triangles there are at least $7$ whose vertex numbers are arranged in increasing order when read counterclockwise.
This completes the proof.
∎
Verification of Key Steps
The first delicate point is the computation of $s(T)$. Take a triangle whose counterclockwise labels are $1,2,3$. The edge orientations are $1\to2$, $2\to3$, and $1\to3$. Along the counterclockwise boundary, the first two edges are traversed in the same direction as their orientations, while the third is traversed from $3$ to $1$, opposite to its orientation. The value is therefore $2-1=1$. Repeating the calculation for a noncyclic order such as $1,3,2$ gives $1-2=-1$. No other values occur.
The second delicate point is the cancellation of interior edges. An interior edge is shared by exactly two small triangles. The counterclockwise boundary walk of one triangle traverses the edge in one direction, while the counterclockwise boundary walk of the other traverses it in the opposite direction. Since agreement and disagreement are exchanged, the two contributions sum to zero.
The third delicate point is the estimate of the boundary contribution. A careless argument might assume equal numbers of increases and decreases. That is false for a cyclic sequence. What is true is that there must be at least one increase and at least one decrease. For a cycle of $12$ distinct numbers, the smallest possible value of $A-D$ occurs when $A=1$ and $D=11$, yielding $-10$. This is exactly the bound needed.
Alternative Approaches
One may reformulate the proof in terms of a discrete circulation. Assign to every oriented edge the value $+1$ when traversed in the direction from the smaller label to the larger label and $-1$ in the opposite direction. The sum around the boundary of a small triangle is then $+1$ or $-1$ according to whether the triangle is increasing counterclockwise or not. Summing over all triangles converts the problem into a boundary integral over the outer hexagon, after which the same estimate on the $12$ boundary edges yields the result.
The edge-cancellation approach used above is preferable because it makes the telescoping completely transparent and reduces the whole problem to a single count on the boundary cycle.