The Mathematical Garden

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 B₁ 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 B₁ exists.

Similarly, we may also assume that there is a blue chain B₂ 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 R₁ from column 1 to column N – 1 and R₂ 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 B₃ must touch chains B₁ and B₂, so B₁, B₂ and B₃ together form a blue chain from row 1 to row M.