To prove that no perfect covers exist for the staircase board.

Question

Let $S_n$ denote the staircase board with $1 + 2 + ... + n = $$n( n + 1)\over2$ squares. Prove that $S_n$ does not have a perfect cover with dominoes for any $n \ge 1$. This problem is provided in Richard A. Brauldi's book on Introductory Combinatorics.

A staircase board of $S_n$ is the board that results in halving a regular $n \times n$ board at a diagonal

The way I, myself, attempted at it is to consider the top left-most square of the board. The dominoe that covers this square must always be vertical, whatever size the staircase board is.

After placing the vertical dominoe, we see that the square that is to the right and down of it must also be covered by a vertical dominoe.

And hence, continuing, we should eventually reach the bottom most "stair" of the staircase. And we would have covered the final "stair" with a vertical dominoe.

This will always isolate one square from the rest of the board, and hence deem it impossible to make a perfect cover. However, the reasoning I presented is very informal and relies on intuition for the most of the part. How do I mathematically prove this? I cannot seem to provide a better explanation. Thank you in advance.

Answer 1

A way to express your proof without all of that case work argument is

The $n$ squares on the main diagonal can only be paired with the $n-1$ squares on the off-diagonal.
Hence, (at least) 1 of the squares on the main diagonals cannot be covered.

I leave it to you to prove/rigorize this to your liking.

---

Note: As you may learn in a further chapter about Hall Marriage Theorem, the perfect cover exists if and only if for all possible collections of squares (with no restrictions), the number of squares that they can be paired with is at least equal in number.
You found an example where $n$ squares can only be paired to $n-1$ squares, thus no perfect cover exists. Thomas's approach in the comments shows that the (say) black squares are paired to 2 fewer white squares, hence no perfect cover exists.
In fact, (almost) any proof about the non-existance of a perfect cover boils down to finding such a collection of squares. The argument could be done on a "let's consider this square then this other square then this other square" basis like you did, or as a "let's consider this collection of squares" as I/Thomas did.