Kvant Math Problem 222

Consider small convex polyhedra such as the tetrahedron, cube, and octahedron.

kvantmathematicsolympiad

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

Problem

Prove that every convex polyhedron has two faces with the same number of sides.

A. Grüntal

Exploration

Consider small convex polyhedra such as the tetrahedron, cube, and octahedron. A tetrahedron has four triangular faces, all identical, so the claim is trivially true. A cube has six quadrilateral faces, again all identical. An octahedron has eight triangular faces, so pairs of faces share the same number of sides. Trying to find a convex polyhedron where every face has a distinct number of sides suggests considering the minimal number of faces required for a convex polyhedron. Euler's formula for convex polyhedra, $V - E + F = 2$, constrains the relationships among vertices $V$, edges $E$, and faces $F$. Each face has at least three sides, so the minimal possible sum of face degrees is $3F$. Each edge belongs to exactly two faces, so $2E = \sum_{i=1}^{F} s_i$, where $s_i$ is the number of sides of the $i$-th face. Attempting to assign strictly increasing numbers of sides to each face leads to a rapid increase in the sum of sides, which may violate the relation with edges required by Euler's formula. The critical step is to show that no convex polyhedron can have all faces with distinct numbers of sides; the key insight is that the number of faces is too large relative to the minimal possible edge sum to allow distinct face degrees.

Problem Understanding

The problem asks to prove that for any convex polyhedron, at least two faces must have the same number of sides. This is a Type B problem: a direct proof of a statement. The core difficulty lies in ruling out the hypothetical situation where all faces have distinct numbers of sides. The challenge is combinatorial: to show that assigning strictly increasing side counts to all faces cannot satisfy the necessary relationships between edges, vertices, and faces dictated by Euler's formula. The intuitive reason is that the minimal side counts grow too fast to maintain the required sum $2E$ without repeating numbers.

Proof Architecture

The proof proceeds by considering a convex polyhedron with $F$ faces, each having at least three sides. Lemma 1 asserts that the sum of the face sides equals twice the number of edges: $2E = \sum_{i=1}^{F} s_i$. Lemma 2 bounds the minimal sum of sides if all faces have distinct numbers of sides: $\sum_{i=1}^{F} s_i \ge 3 + 4 + \dots + (F+2) = \frac{(F+2)(F+3)}{2} - 3$. Lemma 3 relates the number of edges to the number of faces and vertices via Euler's formula, giving $E = V + F - 2$ and $2E \le 6F - 12$ under the assumption that each vertex has degree at least three. The hardest step is showing that $\sum_{i=1}^{F} s_i \ge \frac{F(F+1)}{2}$ contradicts the upper bound $2E \le 6F - 12$ for $F \ge 4$, thus making all face degrees distinct impossible.

Solution

Let a convex polyhedron have $F$ faces, $V$ vertices, and $E$ edges. Each face has at least three sides, and each edge belongs to exactly two faces. Denote the number of sides of the $i$-th face by $s_i$. Then the sum of all sides satisfies

$$\sum_{i=1}^{F} s_i = 2E.$$

Suppose, toward a contradiction, that all $s_i$ are distinct. Then the minimal value of the sum occurs when the face side counts are consecutive integers starting from 3, yielding

$$\sum_{i=1}^{F} s_i \ge 3 + 4 + \dots + (F+2) = \frac{(3 + (F+2)) F}{2} = \frac{(F+5)F}{2}.$$

By Euler's formula, $V - E + F = 2$, so $E = V + F - 2$. Each vertex has degree at least three, so counting edge-ends gives $2E \ge 3V$, implying $V \le \frac{2E}{3}$. Substituting $V \le \frac{2E}{3}$ into $E = V + F - 2$ gives

$$E \le \frac{2E}{3} + F - 2,$$

so

$$E \le 3F - 6,$$

and therefore

$$2E \le 6F - 12.$$

Combining the bounds yields

$$\frac{(F+5)F}{2} \le 2E \le 6F - 12.$$

Multiplying through by 2 and rearranging gives

$$F^2 - 7F + 24 \le 0.$$

The discriminant of the quadratic is $(-7)^2 - 4\cdot 24 = 49 - 96 = -47 < 0$, so no integer $F \ge 4$ satisfies this inequality. Therefore, the assumption that all face side counts are distinct leads to a contradiction. Hence, every convex polyhedron has at least two faces with the same number of sides. This completes the proof.

∎

Verification of Key Steps

The critical step is the derivation of the inequality $\frac{(F+5)F}{2} \le 2E \le 6F - 12$. Recomputing the minimal sum of distinct face sides explicitly for small $F$ confirms correctness: for $F = 4$, the minimal sum $3 + 4 + 5 + 6 = 18$, while $2E \le 6F - 12 = 12$, producing a clear contradiction. For $F = 5$, the sum $3 + 4 + 5 + 6 + 7 = 25$, and $2E \le 6F - 12 = 18$, again a contradiction. Therefore the inequality holds for all $F \ge 4$. The bound $2E \le 6F - 12$ was checked by considering maximal edge counts compatible with minimum vertex degrees, confirming no oversight.

Alternative Approaches

A purely combinatorial approach uses the pigeonhole principle, noting that each face has at least three sides and a convex polyhedron must have at least four faces. Attempting to assign distinct side counts requires at least four consecutive integers starting at three. The sum quickly exceeds twice the maximum possible number of edges given vertex degrees, reproducing the same contradiction without explicitly invoking Euler's formula in full. The main approach is preferable because it quantifies the bounds precisely and extends naturally to arbitrary convex polyhedra, providing a uniform proof.