Consider an $m \times n$ chess board with $mn$ even, $m,n \geq 2$, and one black and one white square removed. Label the white squares $1,\dots, \ell$ where $l = mn/2 – 1$, and for each $i \in \{1,\dots,\ell\}$, let $A_i$ be the set of (black) neighbours of white square $i$. How can I prove that for any $S \subseteq \{i,\dots, \ell\}$,
$$ \left|\bigcup_{i \in S}A_i \right| \geq |S|,$$
i.e., for any set of $k$ white squares, there are at least $k$ black squares neighbouring at least one white square in this set. It seems intuitively obvious, but I'd like to understand how to prove this rigorously (so that I can use Hall's theorem to prove that there exists a domino tiling for such a board).
Neighbours of white squares on a chess board and Hall’s theorem.
chessboardcombinatoricsmatching-theorytiling
Related Solutions
We will prove the general case: In a $ n \times n$ board filled with integers $1$ to $n^2$, then there exist 2 neighboring squares whose difference is at least $n$.
Explanation of main idea: Find $n$ distinct pairs of neighbors where one term is $\leq K$ and the other neighboring term is $\geq K+1$. Then, the smallest of this terms is at most $K-n+1$, and it's neighbour is at least $K+1$, so their difference is at least $n$.
For each row, let $r_i$ be the largest number in that row.
For each column, let $c_i$ be the largest number in that column.
Let $N$ be the smallest of these $2n$ values. WLOG $N=r_I$, and cell $(I,J)$ is equal to $N$. Then, every other integer in this row is $\leq N-1$.
For every column not equal to $J$, we can find adjacent cells where one is $\leq N-1$ (starting with row $I$) and one is $\geq N+1$ (otherwise, this contradicts the minimality of $N$).
In column $J$, either $N$ is adjacent to a number $<N$, or to a number $>N$.
Case 1:$N$ is adjacent to a number $< N$
We now have $n$ distinct pairs of neighbors (since they are in different columns) where one term is $\leq N-1$ and the other is $\geq N$. Let the smallest of the terms be $S$, then $S \leq N-n$. Hence, the difference between $S$ and its neighbor is at least $n$.
Case 2:$N$ is adjacent to a number $> N$.
We now have $n$ distinct pairs of neighbors (since they are in different columns) where one term is $\leq N$ and the other is $\geq N+1$. Let the smallest of the terms be $S$, then $S \leq N-n+1$. Hence, the difference between $S$ and its neighbor is at least $n$.
Draw a hamiltonian cycle on the chessboard. Any cycle will do, and the following one suffices:
Pick (any) one square and call it $s_0$. Number the following squares in the hamiltonian cycle $s_1, s_2,\ldots s_{63}$:
Note that the even $s_i$ are all one color (say pink) and the odd $s_i$ are the other color (say brown). So far this is all very easy.
Now suppose two squares of the opposite colors have been deleted; for example:
The cycle has been cut into two paths, both of which have even length. Such a path is easily covered with dominoes: say one path is $s_k, s_{k+1}, \ldots, s_{k+2j+1}$, where the subscripts are understood mod 64. Then the dominoes easily go onto $(s_k, s_{k+1}), (s_{k+2}, s_{k+3}), \ldots (s_{k+2j}, s_{k+2j+1})$. Similarly the other path is tiled by $(s_{k+2j+3}, s_{k+2j+4}), \ldots, (s_{k-3}, s_{k-2})$.
This theorem and the proof I have given appear on pages 111–112 of Solomon W. Golomb Polyominoes (revised ed.), Princeton University Press, 1994. The proof is attributed to Ralph Gomory.
Best Answer
For integers $m,n\ge2$ with $mn$ even, let $P(m,n)$ denote the statement: on an $m\times n$ chessboard, any $k$ white squares border at least $k+1$ black squares, provided $0\lt k\lt mn/2$.
The statement $P(m,n)$ implies that an $m\times n$ chessboard will still satisfy Hall's condition (for matching white squares to adjacent black squares) after one black and one white square is removed.
Theorem. If $m,n\in\mathbb N$, $m,n\ge2$, and $mn$ is even, then $P(m,n)$ holds.
The theorem follows directly from the fact that the chessboard graph (whose vertices are the squares, two squares being adjacent if they share a side) has a Hamiltonian circuit. Alternatively, it can be proved by induction using the following lemmas. The easy details are left to the reader.
Lemma 1. $P(2,2)$ and $P(2,3)$ hold.
Lemma 2. Suppose $m,n\in\mathbb N$, $m,n\ge2$, $mn$ even. If $P(m,n)$ holds then $P(n,m)$ holds.
Lemma 3. Suppose $m,n_1,n_2\in\mathbb N$; $m,n_1,n_2\ge2$; and $mn_1$ and $mn_2$ are even. If $P(m,n_1)$ and $P(m,n_2)$ hold, then $P(m,n_1+n_2)$ holds.