Kvant Math Problem 320

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

Problem

Which convex $n$-gons can be subdivided into triangles so that no two triangles in the subdivision share a common (completely coinciding) side? (Figure 1 shows that a triangle can be subdivided in this way.)

Figure number 1

A. Pechkowski

Exploration

The statement asks for a classification. A triangle can indeed be subdivided into smaller triangles without any two of them sharing an entire side, so $n=3$ is possible.

The first question is whether any larger convex polygon can have such a subdivision. A quadrilateral seems difficult. In an ordinary triangulation of a quadrilateral, the two triangles share a diagonal. To avoid this, one must allow vertices lying in the interiors of sides of other triangles, producing $T$ junctions. The figure mentioned in the problem for a triangle suggests exactly this phenomenon.

A useful way to encode the subdivision is by a planar graph whose vertices are all vertices of the triangles and whose edges are the smallest side segments between consecutive vertices. Euler's formula then relates the numbers of vertices, edges, and triangles.

The crucial difficulty is to convert the condition "no two triangles share a whole side" into a quantitative restriction. The right object is a stretch, a maximal line segment that is decomposed into sides of triangles in two different ways. Every interior side of a triangle belongs to exactly one stretch. If a stretch contains $s$ triangle sides, then it contains exactly $s-2$ vertices lying in the interiors of sides of triangles. Since $s-2\ge s/3$ whenever $s\ge3$, stretches force many such subdividing vertices.

Combining the Euler count with the stretch count produces an inequality that leaves only one possibility for the boundary: it must have exactly three vertices. Hence only triangles work.

Problem Understanding

We must determine all convex $n$-gons that admit a subdivision into finitely many triangles such that no two triangles have a common side in its entirety.

This is a Type A problem, a classification problem.

The answer should be that only convex triangles admit such a subdivision. The reason is that the prohibition on shared sides forces the subdivision to contain many vertices lying in the interiors of sides of triangles. In a convex polygon with more than three sides, Euler's formula does not allow enough room for all these vertices.

Proof Architecture

Let $P$ be a convex $n$-gon subdivided into $t$ triangles with no two triangles sharing a complete side.

Construct a planar graph $G$ whose vertices are all vertices of the triangles and whose edges are the minimal side segments between consecutive vertices. Euler's formula yields an identity relating $t$, the number of boundary vertices, the number of interior vertices, and the number of subdividing vertices.

Define a stretch as a minimal segment that can be decomposed into sides of triangles in two different ways. Every stretch has size at least $3$, because two triangles are not allowed to share a side.

If a stretch has size $s$, then it contains exactly $s-2$ subdividing vertices. Hence the total number of subdividing vertices is at least one third of the total size of all stretches.

Every side of a triangle not lying on the boundary of $P$ contributes exactly once to the total size of all stretches. This gives a lower bound on the number of subdividing vertices.

Combining this lower bound with the Euler identity yields

$$v_{\mathrm{bd}}+3\bigl(v_{\mathrm{int}}-v_{\mathrm{int}}^{*}\bigr)\le3.$$

Since $v_{\mathrm{bd}}\ge n\ge3$, the only possibility is

$$v_{\mathrm{bd}}=3,\qquad v_{\mathrm{int}}=v_{\mathrm{int}}^{*}.$$

Consequently $n=3$.

The hardest step is proving the inequality relating the number of subdividing vertices to the total sizes of the stretches.

Solution

Let $P$ be a convex $n$-gon admitting a subdivision into $t$ triangles such that no two triangles share a complete side.

We shall prove that necessarily $n=3$. Since the problem statement already indicates that a triangle admits such a subdivision, this will complete the classification.

Let all vertices of all triangles be regarded as vertices of a planar graph $G$. Two vertices are joined by an edge whenever the segment between them lies on a side of a triangle and contains no other vertex.

Denote by $v_{\mathrm{bd}}$ the number of vertices of $G$ on the boundary of $P$, and by $v_{\mathrm{int}}$ the number of vertices in the interior of $P$. Then

$$v(G)=v_{\mathrm{bd}}+v_{\mathrm{int}}.$$

The bounded faces of $G$ are precisely the $t$ triangles of the subdivision, so

$$f(G)=t+1.$$

Euler's formula gives

$$e(G)=v(G)+f(G)-2 =v_{\mathrm{bd}}+v_{\mathrm{int}}+t-1.$$

Let $v_{\mathrm{int}}^{*}$ denote the number of interior vertices that lie in the interior of a side of a triangle. Such vertices will be called subdividing vertices.

Every boundary edge of $G$ belongs to exactly one triangle, and there are exactly $v_{\mathrm{bd}}$ boundary edges. Every interior edge of $G$ belongs to two triangles.

Double counting edge incidences with triangular faces yields

$$2e(G)=3t+v_{\mathrm{int}}^{*}+v_{\mathrm{bd}}.$$

Indeed, the quantity $3t$ counts all sides of all triangles. Whenever a side of a triangle contains a subdividing vertex, that side contributes one additional graph edge. Summing over all such vertices adds exactly $v_{\mathrm{int}}^{*}$.

Substituting the expression for $e(G)$ gives

$$2(v_{\mathrm{bd}}+v_{\mathrm{int}}+t-1) =3t+v_{\mathrm{int}}^{*}+v_{\mathrm{bd}},$$

hence

$$v_{\mathrm{bd}}+2v_{\mathrm{int}}-v_{\mathrm{int}}^{*} =t+2. \tag{1}$$

Now define a stretch to be a minimal segment that can be decomposed into sides of triangles in two different ways.

Because no two triangles share a complete side, every stretch has size at least $3$, where the size of a stretch means the total number of triangle sides contained in it.

If a stretch has size $s$, then along that segment there are exactly $s-2$ interior vertices subdividing sides. Since $s\ge3$,

$$s-2\ge \frac{s}{3}. \tag{2}$$

Each subdividing vertex belongs to the interior of exactly one stretch.

Let $\Sigma$ be the sum of the sizes of all stretches.

A side of a triangle lying on the boundary of the convex polygon $P$ does not belong to any stretch. Every other side belongs to exactly one stretch. Since there are $3t$ triangle sides altogether and exactly $v_{\mathrm{bd}}$ of them lie on the boundary of $P$, we obtain

$$\Sigma=3t-v_{\mathrm{bd}}.$$

By (2), each stretch contributes at least one third of its size to the number of subdividing vertices. Therefore

$$v_{\mathrm{int}}^{*}\ge \frac{\Sigma}{3} =\frac{3t-v_{\mathrm{bd}}}{3} =t-\frac{v_{\mathrm{bd}}}{3}.$$

Thus

$$t\le v_{\mathrm{int}}^{*}+\frac{v_{\mathrm{bd}}}{3}. \tag{3}$$

Substituting (3) into (1) yields

$$v_{\mathrm{bd}}+2v_{\mathrm{int}}-v_{\mathrm{int}}^{} \le v_{\mathrm{int}}^{}+\frac{v_{\mathrm{bd}}}{3}+2.$$

After rearranging,

$$v_{\mathrm{bd}}+3\bigl(v_{\mathrm{int}}-v_{\mathrm{int}}^{*}\bigr) \le3. \tag{4}$$

Since every subdividing vertex is an interior vertex,

$$v_{\mathrm{int}}-v_{\mathrm{int}}^{*}\ge0.$$

Also,

$$v_{\mathrm{bd}}\ge n\ge3.$$

The left side of (4) is therefore at least $3$. Hence equality must hold throughout:

$$v_{\mathrm{bd}}=3, \qquad v_{\mathrm{int}}=v_{\mathrm{int}}^{*}.$$

From $v_{\mathrm{bd}}=3$ and $v_{\mathrm{bd}}\ge n$ we obtain

$$n=3.$$

Thus any convex polygon admitting such a subdivision is a triangle.

Conversely, the figure given in the problem shows that a triangle admits such a subdivision.

Hence the only convex $n$-gons with the required property are the triangles.

$$\boxed{n=3}$$

Verification of Key Steps

The first delicate point is the identity

$$v_{\mathrm{bd}}+2v_{\mathrm{int}}-v_{\mathrm{int}}^{*}=t+2.$$

The possible mistake is to count graph edges as if every triangle side were a graph edge. A side containing subdividing vertices is split into several graph edges. Each subdividing vertex increases the total count of graph edges occurring on triangle boundaries by exactly one. This is why the term $v_{\mathrm{int}}^{*}$ appears in the double counting formula

$$2e(G)=3t+v_{\mathrm{int}}^{*}+v_{\mathrm{bd}}.$$

The second delicate point is the estimate

$$v_{\mathrm{int}}^{*}\ge \frac{\Sigma}{3}.$$

For a stretch of size $s$, the number of subdividing vertices is exactly $s-2$. The condition that no two triangles share a complete side forces $s\ge3$. Checking the first cases,

$$s=3 \Rightarrow s-2=1=\frac{s}{3},$$

$$s=4 \Rightarrow s-2=2>\frac43,$$

and larger $s$ only strengthen the inequality. Summing over stretches is legitimate because each subdividing vertex lies in exactly one stretch.

The final step is extracting the consequence of

$$v_{\mathrm{bd}}+3(v_{\mathrm{int}}-v_{\mathrm{int}}^{*})\le3.$$

Since both summands on the left are nonnegative and $v_{\mathrm{bd}}\ge n\ge3$, the left side cannot be smaller than $3$. Equality is forced, giving

$$v_{\mathrm{bd}}=3$$

and hence

$$n=3.$$

Alternative Approaches

A different approach is to work directly with stretches and avoid introducing the graph identity in its final form. One can count incidences between triangle sides and stretches, then compare this with the number of vertices lying in the interiors of sides. After enough bookkeeping, the same contradiction appears for any convex polygon with more than three sides.

The graph theoretic method is preferable because Euler's formula compresses all topological information into the single relation (1). Once that relation is established, the stretch count converts the geometric condition "no shared side" into a numerical inequality, and the classification follows immediately.