Mathematical Food for Thought

Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.
• Meta

Gimme Your Signature. Topic: Geometry/Logic. Level: AIME. September 11th, 2006

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 and the other vertices . 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 be this face. We claim that if Player 1 signs on first, he or she can win on the third move. Let be the faces that share an edge with , where 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 and the following turn can win with or (indices taken modulo ) since Player 2 cannot block both of them. If Player 2 does sign on , then Player 1 signs on with (again, modulo ), which exists because . Then again Player 1 can sign 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 seconds it will end up at the opposite vertex?