91Ó°ÊÓ

Consider an \(m\) -by- \(n\) chessboard in which both \(m\) and \(n\) are odd. The board has one more square of one color, say, black, than of white. Show that, if exactly one black square is forbidden on the board, the resulting board has a tiling with dominoes.

Let \(\mathcal{A}=\left(A_{1}, A_{2}, \ldots, A_{n}\right)\) be a family of sets with an SDR. Let \(x\) be an element of \(A_{1}\). Prove that there is an SDR containing \(x\), but show by example that it may not be possible to find an \(S D R\) in which \(x\) represents \(A_{1}\).

Consider a board with forbidden positions which has the property that, if a square is forbidden, so is every square to its right in its row and every square below it in its column. Prove that the chessboard has a tiling by dominoes it and only if the number of allowable white squares equals the number of allowable black squares.

Prove that in every application of the deferred acceptance algorithm with \(n\) women and \(n\) men, there are at most \(n^{2}-n+1\) proposals.