HMMT 二月 2017 · 团队赛 · 第 3 题

HMMT February 2017 — Team Round — Problem 3

[ 30 ] A polyhedron has 7 n faces. Show that there exist n + 1 of the polyhedron’s faces that all have the same number of edges.

解析

[ 30 ] A polyhedron has 7 n faces. Show that there exist n + 1 of the polyhedron’s faces that all have the same number of edges. Proposed by: Alexander Katz Let V, E, and F denote the number of vertices, edges, and faces respectively. Let a denote the number k of faces with k sides, and let M be the maximum number of sides any face has. Suppose that a ≤ n for all k and that M > 8. Note that each edge is part of exactly two faces, and k each vertex is part of at least three faces. It follows that M ∑ a = F k k =3 M ∑ ka k = E 2 k =3 M ∑ ka k ≥ V 3 k =3 and in particular ( ) M ∑ k k a 1 − + ≥ F − E + V = 2 k 2 3 k =3 by Euler’s formula. But on the other hand, a ≤ n by assumption, so k ( ) M ∑ k 2 ≤ a 1 − k 6 k =3 ( ) M ∑ k ≤ n 1 − 6 k =3 ( ) ( ) 8 M ∑ ∑ k k = n 1 − + n 1 − 6 6 k =3 k =9 1 1 ≤ n − n ( M − 8) 2 2 k 1 where the last step follows from the fact that 1 − ≤ − for k ≥ 9. Thus 6 2 9 n − 2 9 1 2 2 ≤ n − nM = ⇒ M ≤ < 9 1 2 2 n 2 contradicting the fact that M > 8. It follows that M ≤ 8, and as each face has at least 3 edges, the result follows directly from Pigeonhole.