combinatoricstiling
Prove that a $7\times7$ chessboard with one square removed can always be tiled by $L$ trominoes.
I'm looking for a reasonably simple proof. I was able to prove some specific cases, For instance, when the central square is deleted, the chessboard can be partitioned into four $4\times3$ rectangles, which can be easily tiled.
However, I was unable to prove the general case. Any help would be greatly appreciated.
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.
Not an answer, but a diagram showing a possible $9\times 7$ tiling.
Best Answer
Consider this (i am going draw some formal pictures after I have taken a nap.)
$$\begin{array}{|c|c|c|c|c|c|} \hline X&X&\circ&\circ&\triangle&\triangle&\circ\\ \hline X&X&\circ&\square&\triangle&\circ&\circ\\ \hline \circ&\circ&\square&\square&\blacksquare &\blacksquare &\square\\ \hline \circ&\triangle&\circ&\circ&\blacksquare&\square&\square\\ \hline \triangle&\triangle&\circ&\square&\square&\triangle&\triangle\\ \hline \circ&\circ&\triangle&\square&\circ&\triangle&\square\\ \hline \circ&\triangle&\triangle&\circ&\circ&\square&\square\\ \hline \end{array}$$
$$\begin{array}{|c|c|c|c|c|c|} \hline \square&\square&\circ&\triangle&\triangle&\circ&\circ\\ \hline \square&\circ&\circ&\triangle&\blacksquare&\blacksquare&\circ\\ \hline X&X&\square&\square&\blacksquare &\square &\square\\ \hline X&X&\circ&\square&\triangle&\triangle&\square\\ \hline \triangle&\triangle&\circ&\circ&\triangle&\circ&\circ\\ \hline \triangle&\circ&\triangle&\triangle&\square&\circ&\triangle\\ \hline \circ&\circ&\triangle&\square&\square&\triangle&\triangle\\ \hline \end{array}$$
$$\begin{array}{|c|c|c|c|c|c|} \hline \square&\square&\circ&\triangle&\triangle&\circ&\circ\\ \hline \square&\circ&\circ&\triangle&\blacksquare&\blacksquare&\circ\\ \hline \triangle&\triangle&X&X&\blacksquare &\square &\square\\ \hline \triangle&\square&X&X&\triangle&\triangle&\square\\ \hline \square&\square&\circ&\circ&\triangle&\circ&\circ\\ \hline \circ&\circ&\triangle&\circ&\square&\circ&\triangle\\ \hline \circ&\triangle&\triangle&\square&\square&\triangle&\triangle\\ \hline \end{array}$$