Dividing a Checkerboard into L-Shaped Regions

Question

In preparation for the GRE Math-Subject test, and honestly for the fun of it, I've been working through a select number of my texts. The first of which is Saracino's Abstract Algebra text. I was hoping this wouldn't happen, but I've been very quickly stumped.

The following is Exercise 0.22, and I'm looking for a few hints.

"Prove that the follow statement is true for any integer $n \geq 1$: If the number of squares in a "checkerboard" is $2^n \times 2^n$ and we remove any one square, then the remaining part of the board can be broken up into L-shaped regions each consisting of 3 squares."

Before I wrote this proof, I went ahead and pulled out a sheet of paper and did a little testing, because I'm not exactly sure if all of these have to be correct. I found that I could remove pretty much any square on the $2^2 \times 2^2$ board and not be able to break it up. This leads me to believe that the statement is false. Any advice?

Answer 1

You can prove this using induction.

Our trivial base case is $n=2$.

Now, assume that the statement is true for $n-1$

We can split a $2^n\times 2^n$ board into four $2^{n-1} \times 2^{n-1}$ boards, as shown above. W.L.O.G. the square that we choose to take out is in the upper right quadrant. Since a $2^{n-1} \times 2^{n-1}$ board can be filled with Ls if one square is taken out, the upper right quadrant can be filled without any issue. Now, suppose we take out the L shape in the middle of the board (which is highlighted in red in the picture above). Then each of the other quadrants will have one square missing, and thus can be filled with Ls. Since the shape in the middle itself is an L, the whole board can be filled with Ls. (Sorry for the bad english.)

Answer 2

It is obviously true for $2\times 2$. As an advice, when you see $2^n$ try to divide it into two parts consisting of $2^{n-1}$ and use induction. In your case, divide the whole board into $4$ $2^{n-1}\times 2^{n-1}$ boards.

Edit:

Without loss of generality, suppose we remove a square in the up-right quadrant. Then, on the up-right we have $2^{n-1}\times 2^{n-1}$ square whose exactly one square is removed.

For the remaining three quadrants, we will want to use the induction hypothesis on each one of them. So, place an $L$-shaped tile in the center of the big square, like the following($+$ is the removed square and $\times$s are the $L$-shaped tile): $$\begin{matrix} \square&\square&\square&\square&\square&\square&\square&\square&\\ \square&\square&\square&\square&\square&\square&\square&\square&\\ \square&\square&\square&\square&\square&+&\square&\square&\\ \square&\square&\square&\times&\square&\square&\square&\square&\\ \square&\square&\square&\times&\times&\square&\square&\square&\\ \square&\square&\square&\square&\square&\square&\square&\square&\\ \square&\square&\square&\square&\square&\square&\square&\square&\\ \square&\square&\square&\square&\square&\square&\square&\square&\\ \end{matrix}$$ This tile covers exactly one square of the three remaining quadrants. So, we have $4$ $2^{n-1}\times2^{n-1}$ boards, each have exactly $1$ square covered(removed). Thus, by the induction hypothesis, we can cover each smaller boards with $L$-shaped tiles. By gluing all these coverings together we obtain a covering for the big board.