MathDB

6

Part of 2014 Ukraine Team Selection Test

Problems(1)

blue and yellow paths in a n x n board, one path starts or end at center

Source: Ukraine TST 2014 p6

5/1/2020
Let n≥3n \ge 3 be an odd integer. Each cell is a n×nn \times n board painted in yellow or blue. Let's call the sequence of cells S1,S2,...,SmS_1, S_2,...,S_m path if they are all the same color and the cells SiS_i and SjS_j have one in common an edge if and only if ∣i−j∣=1|i - j| = 1. Suppose that all yellow cells form a path and all the blue cells form a path. Prove that one of the two paths begins or ends at the center of the board.
combinatoricsColoring