MathDB

The cells of an

n \times n

chessboard are coloured in several colours so that no

2\times 2

square contains four cells of the same colour. A proper path of length

m

is a sequence

a_1,a_2,..., a_m

of distinct cells in which the cells

a_i

and

a_{i+1}

have a common side and are coloured in different colours for all

1 \le i < m

. Show that there exists a proper path of length

n

Problem Statement