Putnam 2002, Problem B-2

Consider a polyhedron with at least five faces such that exactly three edges emerge from each of its vertices. Two players play the following game: Each player, in turn, signs his or her name on a previously unsigned face. The winner is the player who first succeeds in signing three faces that share a common vertex. Show that the player who signs first will always win by playing as well as possible.

Solution:
(Note: the problem statement assumes that all polyhedra are connected and that no two edges share more than one face, so we will do likewise. In particular, these are true for all convex polyhedra.) We show that in fact the first player can win on the third move. Suppose the polyhedron has a face \( A \) with at least four edges. If the first player plays there first, after the second player’s first move there will be three consecutive faces \( B, C, D \) adjacent to \( A \) which are all unoccupied. The first player wins by playing in \( C \); after the second player’s second move, at least one of \( B \) and \( D \) remains unoccupied, and either is a winning move for the first player.  

It remains to show that the polyhedron has a face with at least four edges. (Thanks to Russ Mann for suggesting the following argument.) Suppose on the contrary that each face has only three edges. Starting with any face \( F_1 \) with vertices \( v_1, v_2, v_3 \), let \( v_4 \) be the other endpoint of the third edge out of \( v_1 \). Then the faces adjacent to \( F_1 \) must have vertices \( v_1, v_2, v_4 \); \( v_1, v_3, v_4 \); and \( v_2, v_3, v_4 \). Thus \( v_1, v_2, v_3, v_4 \) form a polyhedron by themselves, contradicting the fact that the given polyhedron is connected and has at least five vertices. (One can also deduce this using Euler’s formula \( V - E + F = 2 - 2g \), where \( V, E, F \) are the numbers of vertices, edges and faces, respectively, and \( g \) is the genus of the polyhedron. For a convex polyhedron, \( g = 0 \) and you get the “usual” Euler’s formula.)  

Note: Walter Stromquist points out the following counterexample if one relaxes the assumption that a pair of faces may not share multiple edges. Take a tetrahedron and remove a smaller tetrahedron from the center of an edge; this creates two small triangular faces and turns two of the original faces into hexagons. Then the second player can draw by signing one of the hexagons, one of the large triangles, and one of the small triangles. (He does this by “mirroring”: wherever the first player signs, the second player signs the other face of the same type.)