2
$\begingroup$

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!

$\endgroup$
4
  • $\begingroup$ Why $n\ge3$? Isn't $n\ge2$ enough? $\endgroup$ – bof Dec 18 '20 at 9:01
  • $\begingroup$ 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’$). $\endgroup$ – t42d Dec 18 '20 at 14:11
  • $\begingroup$ 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. $\endgroup$ – bof Dec 18 '20 at 14:28
  • $\begingroup$ Wow, that is significantly more elegant than my way. Thanks for the insight! $\endgroup$ – t42d Dec 18 '20 at 15:10
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Ah ok I see now. Thanks! I had continually been thinking that the SDR needed to actually represent the dominos themselves, rather than more generally just corresponding to the dominos, so no wonder I was never going to find the SDR. $\endgroup$ – t42d Dec 18 '20 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.