Lesson 3

It turns out that the first player has a winning strategy! We will prove this non-constructively, that is, without presenting an explicit strategy.

Theorem. In the Hex game, the first player has a winning strategy.

Proof.

• No draws.  First, let's prove that there are no draws in the game. Consider a board completely filled with cells. Think of the four sides of the field as four additional colored regions: two blue ones and two red ones. To such a filled board, correspond the following graph. The vertices of this graph are all the vertices of the hexagons, as well as the four corners of the field. Draw an edge between two neighboring vertices whenever the two regions on the sides of this edge have different colors. In other words, the graph traces the boundary between red and blue regions, including the boundary between a cell and an outer side of the field. Then, each internal vertex has a degree of zero or two, and the four corner vertices have a degree of one. This means that our graph is a set of cycles, as well as two paths with ends in the corner cells, and these paths do not intersect.
  

  

  
  The way these corner vertices are connected by paths determines the winner.
  

  

  
  In the example above, the corner-to-corner paths connect the corners vertically, so the blue player is the winner.


• Stealing a strategy.  Now, assume that the second player has a strategy. The first player can “borrow” it from the second player as follows: the first player makes their initial move arbitrarily, and then starts playing according to the second player's strategy. This guarantees a win for the first player, which cannot be (since the second player has a strategy). Therefore, the second player cannot have a winning strategy, and since there is no draw, the first player must have one.
  In this reasoning, we implicitly used the fact that the initial move of the first player (which they make arbitrarily) cannot prevent them from winning. More carefully, it should be said as follows: when the first player needs to make a move according to the second player's strategy, they mentally erase one of their pieces (so that the number of pieces on the field becomes odd) and see how the second player would move in such a situation; if the second player's strategy suggests placing a piece in the spot where the first player's (mentally erased) piece already stands, the first player simply places a piece in an arbitrary spot again.

◼