MathDB
Center of grid is endpoint of path

Source: China TSTST 3 Day 2 Q3

March 18, 2017
combinatorics

Problem Statement

Every cell of a 2017×20172017\times 2017 grid is colored either black or white, such that every cell has at least one side in common with another cell of the same color. Let V1V_1 be the set of all black cells, V2V_2 be the set of all white cells. For set Vi(i=1,2)V_i (i=1,2), if two cells share a common side, draw an edge with the centers of the two cells as endpoints, obtaining graphs GiG_i. If both G1G_1 and G2G_2 are connected paths (no cycles, no splits), prove that the center of the grid is one of the endpoints of G1G_1 or G2G_2.
Back to ProblemsView on AoPS