Proof a $2^n$ by $2^n$ board can be filled using L shaped trominoes and 1 monomino

Solution 1:

This is an old chestnut of combinatorial geometry. The proof is a fairly simple induction. We show that the $2^n\times 2^n$ board can be covered by trominoes except for one square.

If $n=1$, the solution is trivial.

Otherwise, assume that we can cover a $2^{n-1}\times 2^{n-1}$ board with trominoes except for one chosen square. Divide the $2^n\times 2^n$ board into four $2^{n-1}\times 2^{n-1}$ square quadrants. One quadrant contains the square we want to leave uncovered by trominoes, and by induction we can cover this quadrant, except for the one square, with trominoes.

For the remaining three quadrants, cover each of these except for one of its corners with trominoes. Rotate the three quadrants so that their uncovered corners lie together at the center of the board. These three remaining squares can then be covered with one more tromino.

I first saw this in Polyominoes by Solomon W. Golomb. it appears on page 5 of the revised edition, Princeton University Press, 1994.

Solution 2:

Another example and some proof.

On some special case of putting monomino in special place, $(2m-1)×(2m-1)$ without multiple of 3 are possible. If a monomino is black, since $(6m-1)^2=3*4m(3m-1)+1$, L blocks is a multiple of 4. Then it's contradiction, so white - black=2. Therefore when $(6m-1)^2$, we can't put a monomino in a place we like. If $(6m)^2$, although L blocks is obviously odd, since $(6m^2-3)+1≠6m^2$, they can't make square. If $(6m-3)^2$, since $(6m-3)^2≠3M+1$, they can't make square.

Solution 3:

Solution: Let $P(n)$ be the proposition that every $2^n \times2^n$ checkerboard with one square removed can be tiled using right triominoes. We can use mathematical induction to prove that $P(n)$ is true for all positive integers $n$.

BASIS STEP: $P(1)$ is true, because each of the four $2 \times 2$ checkerboards with one square removed can be tiled using one right triomino.

INDUCTIVE STEP: The inductive hypothesis is the assumption that $P(k)$ is true for the positive integer $k$; that is, it is the assumption that every $2^k \times 2^k$ checkerboard with one square removed can be tiled using right triominoes.

It must be shown that under the assumption of the inductive hypothesis, $P(k+1)$ must also be true; that is, any $2^{k+1} \times 2^{k+1}$ checkerboard with one square removed can be tiled using right triominoes. To see this, consider a $2^{k+1} \times2^{k+1}$ checkerboard with one square removed. Split this checkerboard into four checkerboards of size $2^k\times2^k$, by dividing it in half in both directions. This is illustrated in Figure 6(??). No square has been removed from three of these four checkerboards. The fourth $2^k\times2^k$ checkerboard has one square removed, so we now use the inductive hypothesis to conclude that it can be covered by right triominoes. Now temporarily remove the square from each of the other three $2^k \times 2^k$ checkerboards that has the center of the original, larger checkerboard as one of its corners. By the inductive hypothesis, each of these three $2^k \times2^k$ checkerboards with a square removed can be tiled by right triominoes. Furthermore, the three squares that were temporarily removed can be covered by one right triomino. Hence, the entire $2^{k+1} \times 2^{k+1}$ checkerboard can be tiled with right triominoes. We have completed the basis step and the inductive step.

Therefore, by mathematical induction $P(n)$ is true for all positive integers $n$. This shows that we can tile every $2^n \times 2^n$ checkerboard, where $n$ is a positive integer, with one square removed, using right triominoes.