SAUDI ARABIAN MATHEMATICAL COMPETITIONS

Question

For n 3, it is given an 2n 2n board with black and white squares. It is known that all border squares are black and no 2 2 subboard has all four squares of the same color. Prove that there exists a 2 2 subboard painted like a chessboard, i.e. with two opposite black corners and two opposite white corners. FIGURE_0

Accepted Answer

Assume for the sake of contradiction that there are no

2 \times 2

square painted like a chessboard. Then all

2 \times 2

subboards are of these paintings as follow (and their rotations).

We will count the length of black-white border in two ways.

1. First way. Observe that from (*), each subboard

2 \times 2

has exactly 2 units of the black-white border. Since the border of whole board is black so each black-white border appears in exactly two

2 \times 2

subboards. The number of

2 \times 2

subboards is

(2 n - 1)^{2}

, so the total length of black-white border is

\frac{2 ( 2 n - 1 ) ^{2}}{2} = (2 n - 1)^{2}

which is an odd number.

2. Second way. Let color the lattice point in the given board by black-white like chessboard. When we move along the border of any white squares, we will get the black and white points alternatively, which mean any connected region of white squares has even perimeter. The entire white region is the union of disjoint white regions, so the total length of black-white border is even.

This is a contradiction so we can get the conclusion that there exists some subboard

2 \times 2

which colored like chessboard.