Coloring dominoes in three colors
Source: All-Russian Olympiad 2006 finals, problem 10.8
May 7, 2006
rectanglecombinatorics proposedcombinatorics
Problem Statement
A square is tiled by dominoes (i. e. rectangles) in an arbitrary way. Show that one can color the dominoes in three colors such that the number of the dominoes of each color is the same, and each dominoe has at most two neighbours of the same color as . (Two dominoes are said to be neighbours if a cell of one domino has a common edge with a cell of the other one.)