{"id":381,"date":"2019-06-26T23:50:06","date_gmt":"2019-06-26T23:50:06","guid":{"rendered":"http:\/\/funfacts.104.42.120.246.xip.io\/?page_id=381"},"modified":"2019-11-22T22:03:27","modified_gmt":"2019-11-22T22:03:27","slug":"inductive-tiling","status":"publish","type":"page","link":"https:\/\/math.hmc.edu\/funfacts\/inductive-tiling\/","title":{"rendered":"Inductive Tiling"},"content":{"rendered":"\n
\"\"<\/figure><\/div>\n\n\n\n

Can all but one square of an n by n chessboard be covered by L-shaped trominoes?<\/p>\n\n\n\n

In general, it may not be possible, but if n is a power of 2, it can! See the Figure for an 8×8 example.<\/p>\n\n\n\n

Is there a method for finding such a tiling? Yes, and we can find it by\u00a0induction!<\/p>\n\n\n\n

Presentation Suggestions:<\/strong>
This is a terrific application of induction. Ask students to try to tile an 8×8 or a 16×16 board with L-shaped tiles before showing them this proof.<\/p>\n\n\n\n

The Math Behind the Fact:<\/strong>
A simple proof by induction shows this property. The simplest case is a 2×2 chessboard. Clearly if one square is removed, the remainder can be tiled by one L-shaped tromino. This is the base case.<\/p>\n\n\n\n

Now, given a large chessboard of size 2n<\/sup>x2n<\/sup>, with one square removed, it can be divided into four<\/em> 2(n-1)<\/sup>x2(n-1)<\/sup> 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)<\/sup>x2(n-1)<\/sup> boards all meet at a common corner at the center of the original board.<\/p>\n\n\n\n

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!<\/p>\n\n\n\n

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 4×4 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 4×4 boards will then have a single tile removed, hence by the inductive step they can be tiled too.<\/p>\n\n\n\n

But how can each of these 4×4 boards with a square removed be tiled? We apply our inductive method again, cutting each into four 2×2 boards: one of which has a square removed, and the other three of which don’t have a square removed. Cover their 3 center tiles by a (green) tromino. What remains uncovered are 2×2 boards with a square removed… these can easily be covered by (red and green) trominoes!<\/p>\n\n\n\n

How to Cite this Page:<\/strong> 
Su, Francis E., et al. “Inductive Tiling.” Math Fun Facts<\/em>. <http:\/\/www.math.hmc.edu\/funfacts>.<\/p>\n\n\n\n

Fun Fact suggested by: <\/strong>
Arthur Benjamin <\/p>\n","protected":false},"excerpt":{"rendered":"

Can all but one square of an n by n chessboard be covered by L-shaped trominoes? In general, it may...<\/p>\n","protected":false},"author":7,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"tags":[9,4,12,105,93],"class_list":["post-381","page","type-page","status-publish","hentry","tag-combinatorics","tag-medium","tag-other","tag-proof-by-induction","tag-tiling"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/381","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/comments?post=381"}],"version-history":[{"count":3,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/381\/revisions"}],"predecessor-version":[{"id":1490,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/381\/revisions\/1490"}],"wp:attachment":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/media?parent=381"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/tags?post=381"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}