Rectangle on a checked paper with length of a unit square side being $1$ Is divided into domino figures( two unit square sharing a common edge). Prove that you colour all corners of squares on the edge of rectangle and inside rectangle with $3$ colours such that for any two corners with distance $1$ the following conditions hold: they are coloured in different colour if the line connecting the two corners is on the border of two domino figures and coloured in same colour if the line connecting the two corners is inside a domino figure.
Problem
Source: IZHO 2017 day 1 p3
Tags: combinatorics, Tiling, geometry, rectangle
ThE-dArK-lOrD
16.01.2017 17:59
On the top row corners (on the border of the rectangle), color them by $G, B, G, B,....$ alternatively from left to right.
On the leftmost column corners (on the border of the rectangle), color them $G, R, G, R,...$ alternatively from top to bottom.
Then for the rest corners, we will show that we can color it from left to right of each row (from top to bottom) so that the colored corners always satisfy the following two conditions:
For each domino $ABCD$ where $AD=BC=1,AB=CD=2,$ $(A,C)$ and $(B,D)$ have the same colors but $(A,D)$ and $(B,C)$ not.
For each domino $ABCD$ where $AD=BC=1,AB=CD=2,$ the midpoints of $AB$ and $CD$ have same color.
We can prove it by considering the first time when our conditions are wrong, then show that we can find the previous "mistake" place of colored corners which contradict our primality assumption.
Now the detail is in doing cases bash about what kind of first mistake we encounter.
I believe that there are better solutions that don't involve cases bash.
MellowMelon
16.01.2017 21:32
Let the colors be residues mod 3 and let $f(x,y)$ be the color of vertex $(x,y)$ for $0 \leq x \leq m, 0 \leq y \leq n$. Color $(0,0)$ with color 0, then follow the procedure below to color all other vertices.
1. If the segment from $(x,y)$ to $(x+1,y)$ is not a domino boundary, let $f(x+1,y) \equiv f(x,y) \pmod{3}$.
2. If the segment from $(x,y)$ to $(x+1,y)$ is a domino boundary, let $f(x+1,y) \equiv f(x,y) + (-1)^{x+y} \pmod{3}$.
3. If the segment from $(x,y)$ to $(x,y+1)$ is not a domino boundary, let $f(x,y+1) \equiv f(x,y) \pmod{3}$.
4. If the segment from $(x,y)$ to $(x,y+1)$ is a domino boundary, let $f(x,y+1) \equiv f(x,y) - (-1)^{x+y} \pmod{3}$.
It is easy to check that all conditions on dominoes will be satisfied by following these rules. All we have to check is that we don't attempt to color a vertex with different colors.
To do this we can show that following the above algorithm for the paths $(0,0) \to (x,0) \to (x,y)$ and $(0,0) \to (0,y) \to (x,y)$ gives the same color. That's a matter of checking how many dominoes overlap the line segments from $(x,y)$ to $(0,y)$ and from $(x,y)$ to $(x,0)$ and using a black and white coloring on the squares in the rectangle from $(0,0)$ to $(x,y)$, which isn't too painful of a calculation. There's a bit of casework since $x,y$ both odd means the rectangle doesn't have an equal number of black and white squares.
to cite the fact that starting from an all-horizontal or all-vertical domino tiling, one can get to any other domino tiling by moves of the following form: take a domino pair forming a 2 by 2 square and swap the orientation of both. Here, start with all-horizontal or all-vertical domino tiling in which opposite corners of dominoes always have different colors. Show that after each orientation-swapping move, we can just change the color of its center vertex, and the opposite-corners-different-colors invariant is maintained throughout. Eventually we get to the domino tiling we were given with a valid coloring.
MellowMelon
16.01.2017 23:37
the function $f$ defined in my first solution is consistently defined if you remove the mod 3 and rules 1 and 3. These are known objects called height functions, and they completely trivialize this problem. See here for a good introduction.
alexiaslexia
20.12.2020 16:53
A big definition challenge. Here's another way to state the case bash method (the official Solution uses a clever parity orientation, and the Solutions above explicitly checks row-by-row; which I couldn't think of an efficient way to phrase.) We will start with some notations to categorize favorable shapes (as I'm baffled as how to deal with complicated concave shapes.) $\color{green} \rule{25cm}{3pt}$ $\color{green} \textbf{\text{Tedious notations.}}$ Define a $\textit{normal polyline}$ to be a non-self intersecting broken line, formed by lattice vertices with coinciding start point and end point. From that, we can define the $\textit{region}$ of a normal polyline in the usual manner. Let a $\textit{normal polyline}$ to be $\textit{rectangular}$ if no two segment $\textit{face}$ each other when they are oriented outwards the $\textit{region}$ (i.e. we can shift the lattice segments to form a big rectangle.) Moreover, define the polyline/region to be $\textit{domino-tileable}$ if they can completely be covered by dominoes. Now we consider the position of each domino in relation to its $\textit{region}$. Say a region $\mathcal{R}$ to be $\textit{composed}$ of dominoes $D_1,D_2,\ldots,D_k$ if $D_1 \cup D_2 \ldots \cup D_k = \mathcal{R}$, and further, let $\mathcal{R}$ to be formed by the regions $\mathcal{R}_1, \mathcal{R}_2, \ldots, \mathcal{R}_k = \mathcal{R}$ when \[ \mathcal{R}_i = D_1 \cup D_2 \ldots \cup D_i \]We now proceed with the problem. $\color{blue} \rule{25cm}{1pt}$ $\color{blue} \textbf{\text{Simplicity of rectangular normal polylines.}}$ A rectangular domino-tibleable normal region can be entirely formed by rectangular normal regions. $\color{blue} \textbf{\text{Proof 1.}}$ It is sufficient to remove one domino $D$ so that $\mathcal{R}-D$ is a rectangular normal region; then we can easily proceed by induction. We will further claim that the domino we remove has a long side which are connected to a short side which are in the $\textit{boundary}$ of the polyline, implying the $\color{blue} \textbf{\text{Claim}}$.
For example, in the first picture, the trail $ab/bc/cac/cb$ is switched to $abab/bcb$. It's easy to see that the rule is consistent with itself (there are two parts of induction here: the boundary of the previous region is needed for the uniqueness of the new vertices' coloring, and the new vertices' coloring is needed to prove the consistency of the new boundary) and it is also consistent with the conditions posed in the problem statement. In fact, we are already done with the problem, since a rectangle is a rectangular normal polyline. $\blacksquare$ $\blacksquare$ $\blacksquare$
From a few minutes of experimenting, it should immediately be apparent that there only exist a unique coloring up to $3!$ rearrangement of the three colors, and they should follow a strict pattern illustrated on the second bullet point in $\color{red} \textbf{\text{Coloring Intentions.}}$ So, I spent a good 4+ hours trying to find a consistent way to prove that the coloring is consistent that way, and in retrospect, considering wild polygons might be overcomplicating it by a bit (though I ignored non-rectangular polygons.)
$\rule{25cm}{1pt}$
Almost all of my attempts in devising an explicit algorithm turned into ruins, because of this $``\text{observation}"$ I pulled out: $\textbf{that the coloring is highly variative}$, since it depends heavily on the dominoes' boundary edges.
[asy][asy]usepackage("tikz");label("\begin{tikzpicture}
\draw[green!20!white,thick](0,0)--(0,2)--(1,2)--(1,0)--cycle; \draw[green!20!white,thick] (2,2)--(4,2)--(4,1)--(2,1)--cycle; \node[orange] at (0,0) {$2$}; \node[orange] at (0,0) {$2$}; \node[orange] at (0,1) {$1$}; \node[orange] at (0,2) {$2$}; \node[orange] at (1,0) {$3$}; \node[orange] at (1,1) {$1$}; \node[orange] at (1,2) {$3$}; \node[orange] at (2,1) {$2$}; \node[orange] at (2,2) {$3$}; \node[orange] at (3,1) {$1$}; \node[orange] at (3,2) {$1$}; \node[orange] at (4,1) {$2$}; \node[orange] at (4,2) {$3$};
\draw[green,thick] (1.2,2)--(1.8,2); \draw[green,thick](1.2,2.2)--(1.8,2.8); \draw[green,thick] (1.2,2.8)--(1.8,2.2); \draw[green,thick] (1.2,1.2)--(1.8,1.8); \draw[green,thick](1.2,1.8)--(1.8,1.2);
\end{tikzpicture}
\begin{tikzpicture}
\draw[green!20!white,thick](0,0)--(0,2)--(1,2)--(1,0)--cycle; \draw[green!20!white,thick] (2,2)--(4,2)--(4,1)--(2,1)--cycle; \node[orange] at (0,0) {$2$}; \node[orange] at (0,0) {$2$}; \node[orange] at (0,1) {$1$}; \node[orange] at (0,2) {$2$}; \node[orange] at (1,0) {$3$}; \node[orange] at (1,1) {$1$}; \node[orange] at (1,2) {$3$}; \node[orange] at (2,1) {$1$}; \node[orange] at (2,2) {$2$}; \node[orange] at (3,1) {$3$}; \node[orange] at (3,2) {$3$}; \node[orange] at (4,1) {$1$}; \node[orange] at (4,2) {$2$};
\draw[green,thick,shift={(0,-1)}] (1.2,2)--(1.8,2); \draw[green,thick,shift={(0,-1)}](1.2,2.2)--(1.8,2.8); \draw[green,thick,shift={(0,-1)}] (1.2,2.8)--(1.8,2.2); \draw[green,thick,shift={(0,-1)}] (1.2,1.2)--(1.8,1.8); \draw[green,thick,shift={(0,-1)}](1.2,1.8)--(1.8,1.2);
\end{tikzpicture}");[/asy][/asy]
(The $x$ represent a sliding domino.) From this observation alone, one might obtain the height function immediately, seeing that within one vertical shift of the domino, all dominoes on its right has its color drop by $1 \pmod 3$; or one might obtain the coloring used in the official Solution, as however the dominoes on the left fare, a coloring of $313212$ (clockwise) will retain to be $232131$ or $121323$, where its cell-wise invariant seems to be its clockwise or anticlockwise orientation.
However, those relied on viewing the edges or cells individually; while I did consider the coloring of a cell, and that a cell must have exactly three edges with different-colored endpoints, I didn't notice the uniqueness of that when one color is already fixed; I instead only paid attention to the relation that a cell's diagonal must have different color regardless of its circumstances, and a cell (with $\binom{4}{2}$ relations among its $4$ vertices) must have 5 different-colored edges and 1 similar-colored edges.
$\rule{25cm}{1pt}$
My final attempt in considering individual cells was considering graphs between cells if they are adjacent, which was overcomplicating the construction given on the official Solution. After that, since cells seem to hold no promises, I switched my attention to considering individual vertices. However, no matter how chaotic I partitioned the rectangle into dominoes, it always seemed that the boundaries made a distinct pattern:
\[ 21212/232323/31313/323232 \]Until the end, I tried to milk this consistent-looking pattern to its maximum, however, I realized that this so-called pattern only holds for domino-tileable polylines (no (mod $3$) pattern happens on a single cell, of course.)
[asy][asy]usepackage("tikz");label("\begin{tikzpicture}
\fill[red!10!white] (0,3)--(0,2)--(1,2)--(1,3)--cycle; \draw[red,->](0.5,2.5)--(0.5,1.5); \fill[red!10!white,shift={(1,-1)}] (0,3)--(0,2)--(1,2)--(1,3)--cycle; \draw[red,->,shift={(1,-1)}](0.5,2.5)--(0.5,1.5); \fill[red!10!white,shift={(2,-2)}] (0,3)--(0,2)--(1,2)--(1,3)--cycle; \draw[red,->,shift={(2,-2)}](0.5,2.5)--(0.5,3.5); \fill[red!10!white,shift={(2,0)}] (0,3)--(0,2)--(1,2)--(1,3)--cycle; \draw[red,->,shift={(2,0)}](0.5,2.5)--(-0.5,2.5);
\draw[green!70!white,very thick] (0,1)--(0,3)--(1,3)--(1,1)--cycle; \draw[green!70!white, very thick,shift={(2,-1)}] (0,1)--(0,3)--(1,3)--(1,1)--cycle; \draw[green!70!white,very thick](1,3)--(3,3)--(3,2)--(1,2)--cycle;
\node[orange] at (0,3) {$3$};\node[orange] at (1,3) {$1$};\node[orange] at (2,3) {$3$};\node[orange] at (3,3) {$1$};\node[orange] at (0,2) {$2$};\node[orange] at (1,2) {$2$};\node[orange] at (2,2) {$3$};\node[orange] at (3,2) {$2$};\node[orange] at (0,1) {$3$};\node[orange] at (1,1) {$1$};\node[orange] at (2,1) {$1$};\node[orange] at (3,1) {$1$};\node[orange] at (2,0) {$3$};\node[orange] at (3,0) {$2$};
\end{tikzpicture}");[/asy][/asy]
My last hope was to devise a vertex-by-vertex construction, and gazing at the future for a bit, it seemed too tedious to consider all cases of a vertex in relation to up to $4$ dominoes surrounding that vertex. So, I proceeded to induct down by a domino, and a problem occured when some vertices are already defined beforehand (see the third and sixth picture.)
To make my writing easier, I knew I had to remove a domino in the border somewhere --- this was the place where I could verify the absurd pattern I found earlier! (Both the early 4-sided alternating coloring or the final description in $\color{red} \textbf{\text{Coloring Intentions.}}$) The chase ended with finalising what $``\text{rectangular}"$ means, and what parameters I should use in my extremal argument (both the rightmost-above cell, the top rectangle line and the bounded nature of the algorithm.) See the last picture for a bit more demonstration.
[asy][asy]usepackage("tikz");label("\begin{tikzpicture}
\draw[green!20!white,thick] (0,0)--(0,2)--(1,2)--(1,0)--cycle; \draw[green!20!white,thick,shift={(1,1)}] (0,0)--(0,2)--(1,2)--(1,0)--cycle; \draw[green!20!white,thick](1,0)--(1,1)--(3,1)--(3,0)--cycle; \draw[green!20!white,thick,shift={(1,1)}](1,0)--(1,1)--(3,1)--(3,0)--cycle; \draw[green!20!white,thick,shift={(1,-1)}](1,0)--(1,1)--(3,1)--(3,0)--cycle; \draw[red,->](2.3,0.5)--(2.7,1.5); \draw[red,->] (2.3,0.5)--(2.7,-0.5); \draw[red,->](3.6,1.5)--(3.8,-0.5);
\node[orange] at (1,3) {$3$};\node[orange] at (2,3) {$1$};\node[orange] at (0,2) {$1$};\node[orange] at (1,2) {$2$};\node[orange] at (2,2) {$2$};\node[black] at (3,2) {$3$};\node[black] at (4,2) {$2$};\node[orange] at (0,1) {$3$};\node[orange] at (1,1) {$3$};\node[orange] at (2,1) {$1$};\node[orange] at (3,1) {$3$};\node[black] at (4,1) {$1$};\node[orange] at (0,0) {$1$};\node[orange] at (1,0) {$2$};\node[orange] at (2,0) {$1$};\node[orange] at (3,0) {$2$};\node[black] at (4,0) {$1$};\node at (2,-1) {$3$};\node at (3,-1) {$2$};\node at (4,-1) {$3$};
\begin{footnotesize}
\node at (3,1.5) {yes}; \node at (3,-0.5) {yes}; \node at (4,0.5){no};
\end{footnotesize}
\end{tikzpicture}");[/asy][/asy]
oVlad
28.01.2023 13:54
IZhO 2017/3 wrote: A rectangle on a squared paper with $1\times 1$ squares is divided into domino figures (that is, rectangles made of two unit squares sharing a side). Prove that all the vertices of squares inside the rectangle and on its border can be colored in three colors so that the following condition is satisfied for each two vertices with distance 1: they have different colors if the segment connecting them lies on the border of a domino figure, and the same color otherwise. Look at the rectangle as a graph $G{}$ where the vertices are the nodes of the grid and the edges are the segments induced by the gridlines. Color each edge which lies in the middle of a domino figure red. Shrinking an edge $uv$ of a graph entails the following: delete the vertices $u$ and $v$ and their induced edges, and then construct a new vertex $w$ which is connected to all the neighbors of $u$ and $v$. We shrink all the red edges of $G{}$ thus obtaining a graph $H{}$. [asy][asy] import graph; size(25cm); real labelscalefactor = 0.5; pen dps = linewidth(0.8) + fontsize(10); defaultpen(dps); pen dotstyle = black; real xmin = -8, xmax = 10, ymin = -3, ymax = 6; pen ffqqtt = rgb(1,0,0.2); draw((-6,4)--(-6,3), linewidth(0.8)); draw((-6,3)--(-6,2), linewidth(0.8)); draw((-6,2)--(-6,1), linewidth(0.8)); draw((-6,1)--(-6,0), linewidth(0.8)); draw((-6,0)--(-5,0), linewidth(0.8)); draw((-5,0)--(-4,0), linewidth(0.8)); draw((-4,0)--(-3,0), linewidth(0.8)); draw((-3,0)--(-2,0), linewidth(0.8)); draw((-2,0)--(-1,0), linewidth(0.8)); draw((-1,0)--(-1,1), linewidth(0.8)); draw((-1,1)--(-1,2), linewidth(0.8)); draw((-1,2)--(-1,3), linewidth(0.8)); draw((-1,3)--(-1,4), linewidth(0.8)); draw((-1,4)--(-2,4), linewidth(0.8)); draw((-2,4)--(-3,4), linewidth(0.8)); draw((-3,4)--(-4,4), linewidth(0.8)); draw((-4,4)--(-5,4), linewidth(0.8)); draw((-5,4)--(-6,4), linewidth(0.8)); draw((-5,4)--(-5,3), linewidth(0.8)); draw((-5,3)--(-5,2), linewidth(0.8)); draw((-5,2)--(-5,1), linewidth(0.8) + ffqqtt); draw((-5,1)--(-5,0), linewidth(0.8) + ffqqtt); draw((-6,1)--(-5,1), linewidth(0.8)); draw((-6,2)--(-5,2), linewidth(0.8)); draw((-6,3)--(-5,3), linewidth(0.8) + ffqqtt); draw((-5,3)--(-4,3), linewidth(0.8)); draw((-4,3)--(-4,4), linewidth(0.8) + ffqqtt); draw((-4,3)--(-4,2), linewidth(0.8) + ffqqtt); draw((-4,2)--(-5,2), linewidth(0.8)); draw((-5,1)--(-4,1), linewidth(0.8)); draw((-4,1)--(-4,2), linewidth(0.8)); draw((-4,1)--(-4,0), linewidth(0.8)); draw((-3,0)--(-3,1), linewidth(0.8) + ffqqtt); draw((-3,1)--(-4,1), linewidth(0.8)); draw((-4,2)--(-3,2), linewidth(0.8)); draw((-3,2)--(-3,1), linewidth(0.8) + ffqqtt); draw((-3,2)--(-3,3), linewidth(0.8)); draw((-3,3)--(-4,3), linewidth(0.8)); draw((-3,4)--(-3,3), linewidth(0.8)); draw((-3,3)--(-2,3), linewidth(0.8) + ffqqtt); draw((-2,3)--(-1,3), linewidth(0.8) + ffqqtt); draw((-1,2)--(-2,2), linewidth(0.8)); draw((-2,2)--(-3,2), linewidth(0.8)); draw((-3,1)--(-2,1), linewidth(0.8)); draw((-2,1)--(-1,1), linewidth(0.8) + ffqqtt); draw((-2,0)--(-2,1), linewidth(0.8)); draw((-2,1)--(-2,2), linewidth(0.8)); draw((-2,2)--(-2,3), linewidth(0.8)); draw((-2,3)--(-2,4), linewidth(0.8)); draw((1,2)--(1,1), linewidth(0.8)); draw((1,1)--(1,0), linewidth(0.8)); draw((5,0)--(6,0), linewidth(0.8)); draw((6,4)--(5,4), linewidth(0.8)); draw((5,4)--(4,4), linewidth(0.8)); draw((2,4)--(1,4), linewidth(0.8)); draw((3,0)--(3,1), linewidth(0.8)); draw((5,2)--(5,3), linewidth(0.8)); draw((5,3)--(5,4), linewidth(0.8)); draw((6,2)--(5,2), linewidth(0.8)); draw((1,1)--(2,1), linewidth(0.8)); draw((2,1)--(3,1), linewidth(0.8)); draw((3,1)--(4,1), linewidth(0.8)); draw((1,4)--(1.5,3), linewidth(0.8)); draw((1.5,3)--(2,4), linewidth(0.8)); draw((1.5,3)--(3,3), linewidth(0.8)); draw((1.5,3)--(1,2), linewidth(0.8)); draw((2,4)--(3,3), linewidth(0.8)); draw((3,3)--(4,4), linewidth(0.8)); draw((3,3)--(3,1), linewidth(0.8)); draw((5,3)--(3,3), linewidth(0.8)); draw((4,4)--(5,3), linewidth(0.8)); draw((5,3)--(6,4), linewidth(0.8)); draw((5,3)--(6,2), linewidth(0.8)); draw((5,0)--(5.5,1), linewidth(0.8)); draw((5.5,1)--(6,0), linewidth(0.8)); draw((5.5,1)--(6,2), linewidth(0.8)); draw((5,2)--(5.5,1), linewidth(0.8)); draw((5.5,1)--(4,1), linewidth(0.8)); draw((3,3)--(4,1), linewidth(0.8)); draw((4,1)--(5,3), linewidth(0.8)); draw((5,2)--(4,1), linewidth(0.8)); draw((4,1)--(3,0), linewidth(0.8)); draw((4,1)--(5,0), linewidth(0.8)); draw((1,2)--(2,1), linewidth(0.8)); draw((1.5,3)--(2,1), linewidth(0.8)); draw((3,3)--(2,1), linewidth(0.8)); draw((1,0)--(2,1), linewidth(0.8)); draw((2,1)--(3,0), linewidth(0.8)); dot((-6,4)); dot((-6,3)); dot((-6,2)); dot((-6,1)); dot((-6,0)); dot((-5,4)); dot((-5,3)); dot((-5,2)); dot((-5,1)); dot((-5,0)); dot((-4,4)); dot((-4,3)); dot((-4,2)); dot((-4,1)); dot((-4,0)); dot((-3,4)); dot((-3,3)); dot((-3,2)); dot((-3,1)); dot((-3,0)); dot((-2,4)); dot((-2,3)); dot((-2,2)); dot((-2,1)); dot((-2,0)); dot((-1,4)); dot((-1,3)); dot((-1,2)); dot((-1,1)); dot((-1,0)); dot((6,4)); dot((6,2)); dot((6,0)); dot((5,4)); dot((5,3)); dot((5,2)); dot((5,0)); dot((4,4)); dot((4,1)); dot((3,3)); dot((3,1)); dot((3,0)); dot((2,4)); dot((2,1)); dot((1,4)); dot((1,2)); dot((1,1)); dot((1,0)); dot((1.5,3)); dot((5.5,1)); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); [/asy][/asy] Note that the problem's condition is equivalent to the fact that $H$ is 3-colorable. We shall, therefore, analyze the structure of $H{}$. The crucial observation is that every finite face of $G$ is a square and has precisely one red edge - that is, precisely one edge that is shrunk. Consequently, $H$ is a planar graph whose every finite face is a triangle. Further, note that every face adjacency in $H$ is mapped to a face adjacency in $G$. Evidently, $G$ is 2-face-colorable (we only take finite faces in consideration). Thus, so must be $H$. The desired property now follows immediately due to a well-known lemma of Heawood: Heawood wrote: Consider a planar graph whose every finite face is a triangle. Given that this graph is 2-face-colorable, then its vertices are 3-colorable. There are several proofs of this result, ranging from elementary ones using induction, to topological and cohomological ones.