### 63rd Putnam 2002

Problem B2

A polyhedron has at least 5 faces, and it has exactly 3 edges at each vertex. Two players play a game. Each in turn selects a face not previously selected. The winner is the first to get three faces with a common vertex. Show that the first player can always win.

Solution

We show first that there must be a face with at least 4 edges. Let E, F, V be the number of edges, faces, vertices respectively. We have 2E = 3V (since there are 3 edges at each vertex). If all faces have 3 edges, then 2E = 3F, so using E + 2 = F + V, we have E = 6, F = V = 4 (the tetrahedron). But F > 4, so there must be a face with at least 4 edges. On his first move the first player selects a face K with at least 4 edges. On his second move the first player selects a face which has an edge AB in common with K and such that the other face K' at vertex A and the other face K" at vertex B were not selected by the second player on his first move. That is certainly possible, since K has at least 4 edges. Now on this third move the first player selects K' or K" and wins.

© John Scholes
jscholes@kalva.demon.co.uk
11 Dec 2002