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!
Best Answer
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.