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 numberkof 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, andkeach vertex is part of at least three faces. It follows that
∑Ma = Fk =3 k
∑Mka = Ekk =32
∑Mka
≥ Vkk =33
and in particular
( )
∑Mk ka 1 − + ≥ F − E + V = 2
2 3 kk =3
by Euler’s formula. But on the other hand, a ≤ n by assumption, sok
( )
∑Mk
2 ≤ a 1 −
6 kk =3
( )
∑Mk
≤ n 1 −
k =36
( ) ( )
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
n − 29
9 1
2 ≤ n − n m = ⇒ M ≤ < 92
2 21
2 ncontradicting 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.