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?
Leave a Reply
You must be logged in to post a comment.