Maths Olympiad Prep

Library / /133 of 155

Combinatorics Difficulty 7.0 National olympiad Prove it Saudi Arabia

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

Solution

Assume for the sake of contradiction that there are no 2×22 \times 2 square painted like a chessboard. Then all 2×22 \times 2 subboards are of these paintings as follow (and their rotations).

Figure 1

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

1. First way. Observe that from (*), each subboard 2×22 \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×22 \times 2 subboards. The number of 2×22 \times 2 subboards is (2n1)2(2n-1)^2, so the total length of black-white border is
2(2n1)22=(2n1)2 \frac{2(2n-1)^2}{2} = (2n-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×22 \times 2 which colored like chessboard.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.