The Mathematical Garden

 | Welcome  | Games  | Mathematical methods  | About us |
Games
Black and White
HEX
the game
a question
the proof
winning strategy
Magic
Mark Six
Recursion, Games and Strategy
SIM

Outline of the proof

We shall prove our theorem by Mathematical Induction on M and N, the dimensions of the board.

The proposition is clearly true for a 1 x N, M x 1, or 2 x 2 board.

Assume that it is true for any board of size smaller than M x N. Then try to show that it is try for the M x N board.

Consider the (M -1) x N board obtained by deleting row M. By the induction hypothesis, there is either a red chain from column 1 to column N or a blue chain B1 from row 1 to row M – 1. If it is the former case, then we are done. Therefore, we can always assume that such blue chain B1 exists.

Similarly, we may also assume that there is a blue chain B2 from row 2 to row M. We can further assume that B1 and B2 do not touch for otherwise, we are done.

By deleting column N and then column 1 we can show in the similar ways that there are red chain R1 from column 1 to column N – 1 and R2 from column 2 to column N such that the two chains do not touch.

Since the horizontal red chains do not touch, the number of rows M must be greater than 2. Similarly, since the number of columns N must be greater than 2.

We now consider the (M - 2) x (N – 2) board (the yellow part in the figure) obtained by deleting rows 1 and M and columns 1 and N. For this board, we can apply the induction assumption in its equivalent form: there must be either a blue chain from column 2 to column N-1 or a red chain from row 2 to row M-1.

We assume, without loss of generality, it is the former case. This chain B3 must touch chains B1 and B2, so B1, B2 and B3 together form a blue chain from row 1 to row M.

Department of Mathematics, HKU, 2010