Consider the following tiling problem. You aregiven a m X m board with m squares
ID: 3612172 • Letter: C
Question
Consider the following tiling problem. You aregiven a m X m board with m squares in each rowand m squares in each column where m is a power of 2. Onearbitrary square on the board is distinguished as special. You arealso given a supply of tiles, each of which looks like a 2×2board with one square removed (L shaped). The problem is to coverthe board with these tiles so that each square is covered exactlyonce, with the exception of the special square, which is notcovered at all. Such a covering is called a tiling. Show, usingPMI, that the tiling problem can always be solved.
Explanation / Answer
By the mathematical induction on the integer n such thatm=2n
Basis: the case n=0 is trivially satisfied.Here m=1, and the 1 x 1 “board” is a single squre,which is necessarily special. Such a board is tiled by doingnothing! (if you do not like this argument, check the next simplestcase: if n=1, them m=2 and any 2 x 2 board from which you removeone square looks exactly like a tile by definition)
Induction step: consider any n1.Let m=2n . Assume the induction hypothesis that thetheorem is true for 2n-1 x 2n-1 board.Consider an m x m board,Containing one arbitrary placed SpecialSquare. Divide the board into 4 equal sub-boards by having ithorizontally and vertically. The original special square nowbelongs to exactly one of the sub-boards. Place one tile in themiddle of the original board so as to cover exactly one square ofeach of the other three sub-boards. Call each of the three squaresthus covered “special” for the corresponding sub-board.We are left with four 2n-1 x 2n-1 sub-boards,each containing one special square. By induction hypothesis, eachof these sub-boards can be tiled. The final solution obtained bycombining the tilings of the sub-boards together with the tileplaced in the middle of the original board.