A $3000\times 3000$ square is tiled by dominoes (i. e. $1\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 $d$ has at most two neighbours of the same color as $d$. (Two dominoes are said to be neighbours if a cell of one domino has a common edge with a cell of the other one.)
Problem
Source: All-Russian Olympiad 2006 finals, problem 10.8
Tags: rectangle, combinatorics proposed, combinatorics
08.03.2010 00:23
Let the colors be 0, 1, and 2 if a block is exclusively in column k, then color it k (mod 3). If a block is in column k and column k+1, then count how many blocks above it are also in column k and k+1. If this number is even, then color it k (mod 3). If it's odd, color it (k+1) (mod 3). This coloring satisfies all properties in the problem.
08.03.2010 12:00
No, this doesn't work (it already fails on a $ 6\times 6$ board). And if you claim that this coloring solves the problem, you have to prove that. Further note: the number of tiles that are in columns $ k$ and $ k + 1$ is always even (more generally on any board with even height).
08.03.2010 14:12
Imagine the board as a chessboard. Each domino occupies a white and a black cell. If its white cell is (i,j) then color the domino with color $ (i - j) \mod3$. And that's all. This coloring will form a sort of diagonal strips. The only neighbors of a domino which have the same color are on the same diagonal strip, so there are at most two of them.
08.03.2010 14:29
You can have three neighbours in the same diagonal strip: XxXxX xXbAx XxBaX cCsSx XxXxX Here the dominos are aA, bB, cC and sS (where capital letters are white fields), you see that the first three will be coloured the same but all touch sS.
08.03.2010 14:42
ZetaX wrote: You can have three neighbours in the same diagonal strip: XxXxX xXbAx XxBaX cCsSx XxXxX Here the dominos are aA, bB, cC and sS (where capital letters are white fields), you see that the first three will be coloured the same but all touch sS. But Ss has a different color. the diagonal ABC is different mod 3 from the parallel one that contains S. Note that it says the same color as $ d$.
09.03.2010 14:48
19.02.2013 18:51
color the table with 1,2,3 diagonally. 1,2,3,1,2,3 2,3,1,2,3,1 3,1,2,3,1,2 1,2,3,1,2,3 now for each domino write the some of two numbers in the cells of it mod 3 and we are done
28.03.2019 12:05
Color the table with red, green and blue like this, and color each domino with the same colored cell it covers. Done ?: ROGOBOROGOBO... OGOBOROGOBOR... GOBOROGOBORO... OBOROGOBOROG... BOROGOBOROGO... OROGOBOROGOB... ...............
26.07.2019 18:01
Here is a simple solution:Color the dominos with one part in the first column blue the remaining ones with one part in the second column red the remaining ones with one part in third column green and continue this alnternatingly.It is easy to see this works.
10.08.2023 13:12
wow amazing
24.08.2023 23:31
Label each cell with $x+y \pmod{3}$. Color each domino with its missing label.