The Game of Hex

The following is quoted from Martin Gardner, The Scientific American Book of Mathematical Puzzles and Diversions, chapter 8.

Hex is played on a diamond-shaped board made up of hexagons (see Figure 1).

  
Figure 1: The Game of Hex

The number of hexagons may vary, but the board usually has 11 on each edge. Two opposite sides of the diamond are labeled ``black''; the other two sides are ``white.'' The hexagons at the corners of the diamond belong to either side. One player has a supply of black pieces; the other, a supply of white pieces. The players alternately place one of their pieces on any one of the hexagons, provided the cell is not already occupied by another piece. The objective of ``black'' is to complete an unbroken chain of black pieces between the two sides labeled ``black.'' ``White'' tries to complete a similar chain of white pieces between the sides labeled ``white.''

See Figure 2 for an example of a path (this example also comes from Gardner's article). There will almost certainly be pieces not on the winning path, and there is no obligation to construct the path in any particular order. All that is necessary to win is to have a path joining your two sides of the board somewhere among all the pieces you have played.

  
Figure 2: An Example of a Path in Hex

Prove the following:

1. There can be no tie, and hence either the first player or the second player has a winning strategy.
2. The first player has a winning strategy. Suggestion: Assume that the second player has a winning strategy. Then the first player can make any first move, and then pretend to be the second player, following the second player's strategy.

You may be interested to know that although the first player has a winning strategy, no one knows what it is!