Normat 1/2007 Jorge Nuno Silva 17
One player connects N-S, by droping colored counters, for example, the other E-W.
Usually the board is square (n=m).
The first striking fact about this game is that Hex cannot end in a draw. Suppose
we fill the board with white and black pieces, at random. Now think of the white
stones as water and the blacks as land. Then, either the water flows from SW to
NE, or there is a dam connecting SE to NW. In the latter case Black has won, in
the former White was the winner. There is no possibility of drawing, wich helps
making Hex an interesting game to play.
The above argument is intutive, of course, but the rigorous proof is not difficult.
The most well known proof is combinatorial (see, for example, [2]), but we present
one by induction on the dimension n × m of the board (we use Nash’s version of
the game). This proof deals with the general rectangular board, in the rest of the
paper we assume the board is s quare (n=m).
The result is clear for boards 1 × m, n × 1 and 2 × 2, so we suppose n, m > 3.
Our hypothesis will be that all boards smaller than n × m admit no draws. On a
board n × m let White connect W-E, and Black connect N-S. Assume the board
is completely filled with white and black stones. Consider the board n × (m − 1)
that we get deleting the last column. This board size falls within our induction
hypothesis, therefore there is a black chain connecting N-S (and we are done) or
there is a white one, W
1
, c onnecting the first and the (m-1)th columns.
Now let us delete the first column and apply the same argument. In the n ×(m−1)
board, either Black connected N-S, and there is nothing else to prove, or White
buit a chain, W
2
, c onnecting the columns 2 and m.