Let $n$ be a natural number. A tiling of a $2n \times 2n$ board is a placing of $2n^2$ dominos (of size $2 \times 1$ or $1 \times 2$) such that each of them covers exactly two squares of the board and they cover all the board.Consider now two sepearate tilings of a $2n \times 2n$ board: one with red dominos and the other with blue dominos. We say two squares are red neighbours if they are covered by the same red domino in the red tiling; similarly define blue neighbours. Suppose we can assign a non-zero integer to each of the squares such that the number on any square equals the difference between the numbers on it's red and blue neighbours i.e the number on it's red neigbhbour minus the number on its blue neighbour. Show that $n$ is divisible by $3$ Proposed by Tejaswi Navilarekallu
Problem
Source: Indian TST D2 P2
Tags: combinatorics, Tiling
17.07.2019 15:31
Were you selected for IMOTC? Where did you get the problems from?
17.07.2019 15:31
01.08.2019 09:33
Yes he got selected
06.04.2021 16:04
I am not sure if you can use the following result directly or not, so I am giving a proof for it. Btw do let me know if it can be treated as a trivial result and stated without proof on a contest. The Result wrote: Let $G$ be a finite graph such that each node has degree $2$. Then $G$ is a union of pairwise disjoint cycles. Proof: It suffices to show that each of $G$'s connected component is a cycle. Pick a node $u \in G$ and let $C_u$ be it's connected component. First, if $C_u$ contains a cycle, then it must be that cycle. This is because if we traverse $C_u$ from any node $v$ which is a part of the cycle we never can exit the cycle as $d(v) = 2$ holds all the time. And then $C_u$ will have to be the cycle. So assume that no cycle is part of $C_u$. Begin traversing the graph from $u$ and visiting some node, that you haven't already. This can always be done as $d(u) = 2$ and there is no cycle in $C_u$. So this traversal is infinite, which contradicts the fact that $G$ is finite. We're done now. Seems like a typo @below
06.04.2021 16:09
Kayak wrote: Consider now two sepearate tilings of a $2n \times 2n$ board: one with red dominos and the other with blue dominos. Did the actual question say "sepearate" tilings or is that a typo?
20.04.2023 17:07
A slightly neater finish after making the graph: Consider any cycle of length $k$. Lets say the vertices are $v_1 - v_2 - \dots - v_k - v_1$ and the label of vertex $v_i$ be $x_i$. We note that modulo 2, $x_i = x_{i-1} + x_{i-2}$ irrespective of whether $v_i$ and $v_{i-1}$ were red neighbors or blue. So if $x_1$ and $x_2$ are both $0$ modulo $2$ this would force all $x_i$ in the cycle to be divisible by $2$, and we can divide each $x_i$ by 2. Do this repeatedly until it can no longer be done (it has to end since $x_i$ are non zero) and at this point $(x_1, x_2)$ is one of $(0,1), (1,1), (1,0)$ modulo $2$. These two values force the modulo 2 values of the entire sequence and it is easy to see that values cycle with period $3$ in each case and so the length of the cycle has to be divisible by $3$ which forces $n$ to be divisible by $3$ as required.