Putnam 2013, Problem A-1

Recall that a regular icosahedron is a convex polyhedron having 12 vertices and 20 faces; the faces are congruent equilateral triangles. On each face of a regular icosahedron is written a nonnegative integer such that the sum of all 20 integers is 39. Show that there are two faces that share a vertex and have the same integer written on them.

Solution:
Suppose otherwise. Then each vertex $v$ is a vertex for five faces, all of which have different labels, and so the sum of the labels of the five faces incident to $v$ is at least $0+1+2+3+4=10$. Adding this sum over all vertices $v$ gives $3 \times 39 = 117$, since each face's label is counted three times. Since there are 12 vertices, we conclude that $10 \times 12 \leq 117$, contradiction.

**Remark:** One can also obtain the desired result by showing that any collection of five faces must contain two faces that share a vertex; it then follows that each label can appear at most 4 times, and so the sum of all labels is at least $4(0+1+2+3+4) = 40 > 39$, contradiction.