Hex Theorem/Corollary

From ProofWiki
Jump to navigation Jump to search

Theorem

Every game of Hex has exactly one winner.


Proof

Aiming for a contradiction, suppose there is a sequence of moves:

$P_1, Q_1, P_2, Q_2, \dotsc$

such that neither player wins.

By the Pigeonhole Principle, every tile is marked after $n^2$ moves.

But, by the Hex Theorem, that board has exactly one winner.

This contradicts the assertion that neither player wins.

Thus, by Proof by Contradiction, every game of Hex has at least one winner.

$\Box$


Aiming for a contradiction, suppose there is a game of Hex in which both players win.

Let $B$ be the board at the end of the game.

Let every unmarked tile of $B$ be marked with an arbitrary player symbol, by the Principle of Finite Choice.

Then, the resulting board $B'$ has every tile marked.

But, by definition of winning, each player has a finite sequence of adjacent tiles marked with their own symbol, which spans their opposite sides.

In particular, every tile in the sequence is marked in $B$, and so is marked the same in $B'$.

Thus, both players win in $B'$.

This contradicts the Hex Theorem.

Thus, by Proof by Contradiction, every game of Hex has no more than one winner.


The result follows.

$\blacksquare$