1996-09 Solution

A proof by induction:

• Base Case #1: n = 0 means a 1x1 chessboard. Removing that one tile leaves nothing left to be tiled, so we've tiled the chessboard with 0 tiles.
• Base Case #2: n = 1 means a 2x2 chessboard. Removing that one tile leaves exactly a triomino, which we put down at the proper orientation.
• Induction step: We assume we can tile a 2ⁿ by 2ⁿ chessboard with a square removed from it. To tile the 2ⁿ⁺¹ by 2ⁿ⁺¹ chessboard with a square removed from it, we divide the chessboard down the middle horizontally and vertically. This cuts the chessboard into 4 equal 2ⁿ by 2ⁿ blocks. The missing square will be in one of those sections, WLOG let's say it's in the upper-left section. We know from induction that we can tile that section. The remaining three sections are tiled by removing the square closest to the center from each of these 2ⁿ by 2ⁿ sections. These 3 sections with that square removed can be tiled by induction. The central three squares removed (shown in magenta below) perfectly form a triomino, so we use one additional triomino to fill that region, and we're done.

WWW Maven: Dan Garcia (ddgarcia@cs.berkeley.edu) Send me feedback