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.
|