Consider the following two person game, in which players take turns coloring edges of a cube. Three colors (red, green, and yellow) are available. The cube starts off with all edges uncolored; once an edge is colored, it cannot be colored again. Two edges with a common vertex are not allowed to have the same color. The last player to be able to color an edge wins the game.
Given best play on both sides, should the first or the second player win? What is the winning strategy?
Since there are twelve edges in all, a game can last at most twelve turns. How many twelve-turn end positions are essentially different?
Source: The Wohascum County Problem Book, G. Gilbert, M. Krusemeyer, L. Larson, M.A.A. (1993).© Copyright 2000 Stan Wagon. Reproduced with permission.