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

Suppose we have an $2^n\times 2^n$ board. Prove you can use any rotation of L shaped trominoes and a monomino to fill the board completely.

You can mix different rotations in the same tililng.

• What exactly are your "L"-shapes? Half the border of a $4\times 3$ rectangle? Or which dimensions? – AlexR Aug 6 '13 at 17:22
• Are you perhaps trying to show that a $2^n\times 2^n$ board can't be filled by trominoes and one monomino? It's totally obvious that trominoes can't fill an $8\times 8$ board because 3 does not divide 64; on the other hand, they can fill a $6\times 6$ board quite easily. For the $2^n\times 2^n$ case, see mutilated chessboard problem. – MJD Aug 6 '13 at 17:28
• @alexr "L-shaped tromino" is a clear and unambiguous piece of jargon in combinatorial geometry and is easy to look up on the Internet. – MJD Aug 6 '13 at 17:29
• My mistake; the mutilated chessboard problem is something else. – MJD Aug 6 '13 at 17:42
• You might enjoy trying to cover a $9\times 9$ board with 27 trominoes. I found it surprisingly tricky. – MJD Aug 6 '13 at 18:27

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.

• Note that this proof actually shows that a $2^n$ by $2^n$ board can be covered with $L$-shaped trominoes and a monomino, no matter where the monomino is placed. – user133281 Aug 29 '14 at 7:22
• Thanks. That is why I referred to the extra square as a "chosen" square. You can choose it to be any square you like. – MJD Aug 29 '14 at 13:14

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: 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 $$2k+1 \times2k+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.

• You have added nothing new to the already existing answers. – José Carlos Santos Dec 7 '18 at 22:24