Integral of this equationSolutionA simple proof by induction

Integral of this equation

Solution

A simple proof by induction shows this property. The simplest case is a 2x2 chessboard. Clearly if one square is removed, the remainder can be tiled by one L-shaped tromino. This is the base case.

Now, given a large chessboard of size 2ⁿx2ⁿ, with one square removed, it can be divided into four

2^(n-1)x2^(n-1) smaller chessboards (the corners of the original board). One of those corners contains the removed tile, so by the inductive step, it can be tiled by L-shaped trominoes. Now notice that the remaining three 2^(n-1)x2^(n-1) boards all meet at a common corner at the center of the original board.

The 3 corner tiles there form an L-shaped set that can be covered by one tromino! And by removing them, those 3 chessboards each have a tile removed, and by the inductive step they can be tiled by trominoes as well! Thus we have covered the entire chessboard (apart from the removed square) by trominos!

This proof actually leads to a method for constructing such a tiling, by successive applications of induction. As an example, consider Figure 1 above without any tiling and with one square removed (here, the black square). We divide the board into four 4x4 boards, one in each quadrant. The bottom left board can be tiled by the inductive step, because it has a square removed. And in the three other boards, we can cover the corner squares where they meet by a single L-shaped tromino (here, orange). These three 4x4 boards will then have a single tile removed, hence by the inductive step they can be tiled too.