Tiling a chessboard
Task number: 3323
A chessboard of dimension \(2^n \times 2^n\) is missing one arbitrarily chosen square. Show that the remaining area of the chessboard can be covered with tiles that have the shape of an „L“ and occupy three squares each.
Solution
The assertion holds for a chessboard of dimension \(2\times 2\) (or even \(1\times 1\)).
We divide the \(2^n\times 2^n\) chessboard into quarters. The missing square will be in one of these quarters of size \(2^{n-1}\times 2^{n-1}\), so we can use the inductive hypothesis to cover it.
Now we will completely cover the remaining three quarters of the chessboard. We remove one tile of shape „L“ from the center of the chessboard such that the tile contains one square from each of the three remaining quarters. Now we are left with three chessboards of size \(2^{n-1}\times 2^{n-1}\), each missing a corner square, and we can tile them using the inductive hypothesis.
(As a programming exercise, try to write a recursive program that solves this problem.)
