# System of distinct representatives and chessboards

I encountered the following problem, which was presented in the context of the topic of SDRs (system of distinct representatives) - I am able to solve the problem, but I make no use of a SDR, and I am wondering whether someone sees a solution which applies an SDR:

Suppose we are given an $$m \times n$$ chessboard, with $$m$$ even. Provided we have $$n \geq 2$$, prove that if we delete one white square and one black square, we can still tile the remaining board with dominos.

I have a reasonably straightforward way of solving the problem (basically it is sufficient to assume W.L.O.G. that the deleted cells $$\textit{define}$$ the chessboard, by acting as the top-left and bottom-right corners, and showing that this resulting grid can be tiled) by doing a little case-analysis, but this makes no use of an SDR (which is the context in which this question was asked). I don't know whether or not there is a solution which involves an SDR, but if there is, I cannot find it. In particular, I am not even sure how an SDR could be defined in this context. So my question is, can anyone see how to solve this problem by making use of the existence of some SDR? Again, I am aware of a solution in general, just not one which involves an SDR. Any results regarding SDRs are allowed (e.g. Hall's condition). Let me know if you have any thoughts regarding how an SDR could be defined here!

• Why $n\ge3$? Isn't $n\ge2$ enough?
– bof
Dec 18, 2020 at 9:01
• Ah, you are correct about $n \geq 2$ being enough - thanks, I’ll fix that. Regarding the former comment, the way this problem is posed, deleting the top-left and bottom-right corners of an $8 \times 8$ chessboard simply isn’t a legal choice here, since the problem requires us to delete two squares of $\textit{opposite}$ color. In particular, if we let $m’$ and $n’$ be the dimensions of the (sub)-rectangle defined by letting the deleted tiles be the top-left and bottom-right corners, then exactly one of $m’$ and $n’$ will be even (w.l.o.g. we can say it will be $m’$).
– t42d
Dec 18, 2020 at 14:11
• If $m,n\ge2$ and $mn$ is even, then a rook can make a tour of the board and return to its starting point, visiting each square just once. (In graph theory lingo, the graph having the squares of the chessboard as vertices, with two squares being adjacent if they share a side, has a Hamiltonian cycle.) Deleting two squares of opposite color breaks the rook's closed tour into two paths, each containing an even number of squares.
– bof
Dec 18, 2020 at 14:28
• Wow, that is significantly more elegant than my way. Thanks for the insight!
– t42d
Dec 18, 2020 at 15:10

For each black square, consider the set of white squares which neighbor it. An SDR for this collection of sets corresponds to a domino tiling; choosing a white square $$W$$ from the set for a black square, $$B$$, means that $$B$$ and $$W$$ are covered by a domino. You then need to prove the Hall condition holds for this collection of sets, which means that every set of $$k$$ black squares shares a border with at least $$k$$ distinct white squares. I am not sure if there is any way to do this which does not at some point use the idea in your solution.