There are several dominoes on a board such that each domino occupies two adjacent cells and none of the dominoes are adjacent by side or vertex. The bottom left and top right cells of the board are free. A token starts at the bottom left cell and can move to a cell adjacent by side: one step to the right or upwards at each turn. Is it always possible to move from the bottom left to the top right cell without passing through dominoes if the size of the board is a) $100 \times 101$ cells and b) $100 \times 100$ cells? Nikolay Chernyatiev
Problem
Source: 42nd International Tournament of Towns, Junior O-Level P5, Spring 2021
Tags: combinatorics, board, Tournament of Towns
sn6dh
19.02.2023 16:18
Not always possible. Construction:
$$A:=\begin{array}{|c|c|c|c|}\hline
&&&D\\\hline
&&&D\\\hline
&D&&\\\hline
&D&&\\\hline
\end{array}$$where $D$s are dominoes.
Cut the board into a $100\times100$ board on the left and a $100\times1$ board on the right.
Use $25\times25$ $A$s to cover the $100\times100$ board.
Color the board like this:
$$\begin{array}{|c|c|c|c|c|c|c|c|c}
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\\\hline
1&1& 1& D& 0& 0& 0& D&\cdots\\\hline
1&1& 1& D& 0& 0& 0& D&\cdots\\\hline
1&D& 0& 0& 0& D&-1&-1&\cdots\\\hline
1&D& 0& 0& 0& D&-1&-1&\cdots\\\hline
0&0& 0& D&-1&-1&-1& D&\cdots\\\hline
0&0& 0& D&-1&-1&-1& D&\cdots\\\hline
0&D&-1&-1&-1& D&-2&-2&\cdots\\\hline
0&D&-1&-1&-1& D&-2&-2&\cdots\\\hline
\end{array}$$We can see that when the token moving right or upward without passing a domino, the number in the cell can never decrease. The number in the bottom-left is $0$, but that in the top-right is $-1$, so it is impossible to move there.
Always possible.
Let the bottom-left be $(1, 1)$ and the top-right be $(100, 100)$.
Induction on $n$ to prove that if $(n, n)$ is free then it is always possible to go there from $(1, 1)$ without passing a domino.
For $n=1$, it's trivial.
Suppose for all $n\leq k$, it holds.
For $n=k+1$, if $(k+1, k+1)$ is free, there are $2$ cases:
Case 1: $(k, k)$ is free, since no $2$ dominoes are adjacent by vertices, at least one of $(k, k+1), (k+1, k)$ is free, and therefore the token can go to $(k, k)$ first by the induction hypothesis and then go to $(k+1, k+1)$.
Case 2: $(k, k)$ is not free, WLOG suppose one of $(k, k-1), (k+1, k)$ is not free, since no $2$ dominoes are adjacent by vertices or edges, $(k-1, k-1), (k-1, k), (k-1, k+1), (k, k+1)$ are free, and therefore the token can go to $(k-1, k-1)$ first by the induction hypothesis and then go to $(k+1, k+1)$ through $(k-1, k), (k-1, k+1), (k, k+1)$.
$\therefore$ by induction $(100, 100)$ is always possible to go from $(1, 1)$ without passing a domino.