Monday, September 11, 2006

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?