MathDB

3

Part of 2007 Argentina Team Selection Test

Problems(1)

Coloring dominoes in three colors

Source: All-Russian Olympiad 2006 finals, problem 10.8

5/7/2006
A 3000×30003000\times 3000 square is tiled by dominoes (i. e. 1×21\times 2 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 dd has at most two neighbours of the same color as dd. (Two dominoes are said to be neighbours if a cell of one domino has a common edge with a cell of the other one.)
rectanglecombinatorics proposedcombinatorics