0
$\begingroup$

Consider a polyhedron with at least five faces such that exactly three edges emerge from each vertex. Two players play the following game: the players sign their names alternately on precisely one face that has not been previously signed. The winner is the player who succeeds in signing the name on three faces that share a common vertex. Assuming optimal play, prove that the player who starts the game always wins.

$\endgroup$
1
$\begingroup$

Umm, I think this is a pretty famous problem with a google-able solution. Anyway, we would need to use Euler's theorem for connected planar graphs (as this is one). Using standard notation...

We have $F \geqslant 5 $, and $E = 3V/2$. We will show that not all faces of the polyhedron are triangles. Otherwise, $E = 3V/2$ and Euler's formula will give us $F - 3F/2 + F = 2$,that is, $F = 4$, which is a contradiction.

The game strategy for the two players:

The first player writes his/her name on a face that is not a triangle; call this face $A_1A_2 . . . A_n, n ≥ 4$. The second player, in an attempt to obstruct the first, will sign a face that has as many common vertices with the face signed by the first as possible, thus claiming a face that shares an edge with the one chosen by the first player. Assume that the second player signed a face containing the edge $A_1A_2$. The first player will now sign a face containing the edge $A_3A_4$. Regardless of the play of the second player, the first can sign a face containing either $A_3$ or $A_4$, and wins.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy