$2^n \times 2^n$ Chessboard Covering minus $1$ square

Question

We are given a $2^n \times 2^n$ chessboard and we must prove that we can cover this chessboard with gamma shapes leaving only one square uncovered.

A gamma shape is:

So to solve this I proceeded with induction.

Here is my proof:

For $n=1$ we have a $2 \times 2$ chessboard and if we remove square then a gamma shape remains so we can cover this and leave exactly one uncovered. Now suppose that for some $n \in \mathbb{N}$ we can cover the $2^n \times 2^n$ chessboard with gamma shapes living exactly one square out so we can cover it leaving a corner out.

Now for $n+1$ we have a $(2 \times2^n) \times (2 \times 2^n)$ chessboard which is a union of the $4$ smaller $2^n \times 2^n$ chessboards.So we can picture in mind a big chestboard of $4$ smaller.

From this union we pick one of the smaller chessboards and we cover it with gamma shapes leaving exactly one square uncovered at the corner of this chessboard which is a corner of the bigger chessboard .

To cover the rest $3$ chessboards (this time all of their squares) we use the induction hypothesis. Note that these three remaining chessboard form a big gamma shape.

From these chessboards we remove(but not realy, just in our mind) the $3$ centered squares wich form a little gamma shape (in the big gamma shape that form the 3 chessboards) So each of the 3 chessboards we can cover it with gamma shapes using our induction hypothesis and to finish we add another gamma shape to to cover the 3 centered squares we removed in our mind.

Thus we are done because we covered a $(2 \times2^n) \times (2 \times 2^n)$ chessboard with gamma shapes leaving only one out.

My question is:

Is there another more elegant and simpler solution than this or any other solution at all?

I'm very curious to know.

Thank you in advance.

Answer 1

Not exactly an answer, since OP asks for an alternative proof, but too long for a comment.

I see a problem in the proof. The inductive step assumes that the square that you leave uncovered is at a corner of the board.

Since it is true in the base case, in the inductive step you can say that you cover one of the quarters leaving uncovered a square at the corner of the big board, and the other quarters leaving uncovered the appropriate corners so that the holes form a gamma-like shape.

It is clear that you can choose what corner is to remain uncovered (rotating the board, if needed). So the proof can be fixed, but the corner issue is worth to be mentioned, if you ask me.

EDIT: Since OP has edited his question, this answer is even less an answer than before. Thank you for voting, anyway.

Answer 2

Here is a helpful picture:

So the grey square is an arbitrary square that has been removed from the $2^{n+1} \times 2^{n+1}$ chessboard. The pink squares actually form a 'Gamma shape' that you are talking about. The think black lines divide the $2^{n+1} \times 2^{n+1}$ chessboard into 4 smaller $2^n \times 2^n$ chess boards.

Since the grey square has to occur in one of the 4 smaller $2^n \times 2^n$ chess boards, then by inductive hypothesis (which says that any $2^n \times 2^n$ chess board with 1 arbitrary tile removed) we can tile that one smaller top left chess-board with the grey square removed. And we can tile the three others, each with a pink corner removed. And finally we place a Gamma to cover the pink squares themselves, and the whole thing is tiled!