Gimme Your Signature. Topic: Geometry/Logic. Level: AIME.

Problem: (2002 Putnam - B2) 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: First, we claim that the polyhedron contains a face with at least four sides. To prove this, suppose the contrary, that all faces are triangles. Take any three faces that share a vertex. Called the shared vertex $ A_1 $ and the other vertices $ A_2, A_3, A_4 $. Since each vertex already has three edges emerging from it, we cannot add a new vertex; hence we will have at most four faces. Contradiction. So there exists a face with at least four sides.

Let $ a $ be this face. We claim that if Player 1 signs on $ a $ first, he or she can win on the third move. Let $ a_0, a_1, \ldots, a_{k-1} $ be the faces that share an edge with $ a $, where $ k \ge 4 $ because there are at least four such faces. If Player 2 does not sign on any of these faces, Player 1 can sign on any $ a_i $ and the following turn can win with $ a_{i+1} $ or $ a_{i-1} $ (indices taken modulo $ k $) since Player 2 cannot block both of them. If Player 2 does sign on $ a_i $, then Player 1 signs on $ a_j $ with $ j \neq i \pm 1 $ (again, modulo $ k $), which exists because $ k \ge 4 $. Then again Player 1 can sign $ a_{j \pm 1} $ the next turn to win, at most one of which can be blocked by Player 2. QED.

--------------------

Comment: Not really too hard of a problem; the only real challenge was showing that there exists a face with at least four edges. And the proof of that was not complex either. Just simple logic and a bit of geometry to finish it.

--------------------

Practice Problem: Suppose an ant is on the vertex of a cube. Each second, it can move along one edge. What is the probability that after $ 60 $ seconds it will end up at the opposite vertex?