This question is about tiling shapes with Ltrominoes three 1

This question is about tiling shapes with L-trominoes: three 1 times 1 squares attached so that they form an L-shape. To tile a shape means to fill it completely with non-overlapping copies of a base shape. For example. Figure 1 shows that we can tile an 8 times 8 square whose top-left comer is missing with L-trominoes Prove that for n greaterthanorequalto 1, any 2^n times 2^n square with one comer missing can be tiled with L-trominoes. What if the missing square is not a corner? Can we still tile all 2^n times 2^n squares with a missing ok anywhere? If so, prove it. If not, give a counter-example: an 2^n times 2^n square with a non-corner tile missing that cannot be tiled by L-trominoes, and explain why it cannot be tiled.

Solution

Proof by induction

P(n) = 2ⁿ X 2ⁿ square which can be tiled with L-trominoes

Base P(1)

P(1) is obviously true as there is just 1 L-tromino with a corner missing ( as all the squares are corner)

Let P(k) be true

Check for P(k+1)

P(k+1) is nothing but 4 P(k) squares. So there must be 4 missing corners.

(b) Combine them at the centre as all the missing corners join at the center of the bigger square. Since it forms a 2 x 2 square in the core,it can be tiled by another L-tromino. So there is a square tiled with L-trominoes with a missing square not located at the corner.

(a) Now since all the four squares P(k) were separate at first so no L-trominoes would be effected (except at the centre) on seprating any one of the squares from the bigger square P(k+1). So separate the square with a missing piece and place it back after rotating the square 180 degrees. The missing piece has now moved from the center to the corner. Thus P(k+1) is true. Therefore any 2ⁿx2ⁿ squares can be tiled with L-trominoes with a missing square corner.