Covering $6 \times 6$ chessboard with $1 \times 2$ tiles

Question

Problem: prove that after putting in 11 1 by 2 tiles in the 6 by 6 chessboard, there is definitely room to put in another tile. Tiles cannot overlap with each other.

So I found this similar problem: https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1134555169

Apparently if you cover the whole chessboard with 18 tiles, you can find a line without crossing each tile. But is this a related problem to the original problem?

Answer 1

If it were possible to add $11$ tiles so that no more could be added (this is called a clumsy packing, by the way), then the leftover holes would consist of $14$ isolated $1\times 1$ cells.

From each of these $14$ squares, place a counter on the four squares adjacent to it, which will either be on already-placed dominoes or will lie outside the border of the chessboard. But it is easy to see that a domino can't be next to more than $4$ of these holes, or else two of them would be adjacent (which we have assumed is not the case). So of the $14\cdot4=56$ counters placed, at most $44$ of them can fall on dominoes. This leaves $12$ counters to lie on the border of our $6\times 6$ chessboard, each of which must originate from a hole on the corresponding edge of the chessboard. But note that if we have more than $4$ holes on any given edge of the chessboard, two of them must be adjacent, so by the pigeonhole principle, every side must have exactly $3$ holes on it.

This means that up to rotation, the board must look like this:

O _ O _ O _
_ ? ? ? ? O
O ? ? ? ? _
_ ? ? ? ? O
O ? ? ? ? _
_ O _ O _ O

where a _ indicates one of the $14$ holes, and an O indicates a cell where a domino has been placed. But then we have identified a corner cell that is occupied by a domino, and yet has no neighbors for its other half to lie in. This is a contradiction.

(As an alternate method of proof, you could convince yourself that at least one domino must have $3$ or fewer counters on it, in which case you could more readily obtain a contradiction along one of the sides of the chessboard. This isn't too hard to do either.)

---

A paper analyzing this question for $n\times n$ boards is here, and proves that it takes $n^2/3$ dominoes for a clumsy packing when $3|n$. The number of dominoes in a clumsy packing is given at A280984 in the OEIS.

As to the question at the end of your post, I don't think fault-free domino tilings are particularly related to this problem.