A Geometric Induction Example: the Tromino Puzzle  

 
Objective: This demo of the Tromino Puzzle provides a geometric example of an induction argument showing for any square grid having side length  2ⁿ,  with a single square occupied by a tile, that it is always possible to fill in the remaining  2²ⁿ - 1 squares with L-shaped tiles, called trominoes, covering three squares each. (Click here for pictures of trominoes.)

Level: Any course where induction is introduced.

Prerequisites: A discussion of the method of induction and possibly several numerically oriented examples that illustrate the technique.

Platform: None, but links are provided to applets that permit experimentation to solve the puzzle for various sizes of the grid.

Instructor's Notes:

Background: Mathematical induction, or induction for short, is a method for proving statements often involving positive integers, but is easily applied to situations in which one case depends on previous cases.

The principle of induction is a powerful method for confirming results arrived at by inductive reasoning. "Inductive reasoning involves collecting evidence from experiments or observations and using this information to formulate a general law or principle. Inductive reasoning attempts to go from the specific to the general, but even with large quantities of evidence the conclusion is not guaranteed. However, mathematics often uses an inductive process to formulate conjectures which are then subjected to rigorous deductive reasoning before they are accepted. Remember that a conjecture is a conclusion based on incomplete evidence ^_ that is, a guess. Much can be gained from using experimental evidence to suggest conjectures and then applying deductive arguments to determine the truth or falsity of the conjecture. A number of important advances in science and engineering evolved in just this way." [1]

"The cycle of

experiment(s) _ conjecture _ check by deductive reasoning

is very important in mathematics." [1]

The principle of induction that we state next is really a particular deductive checking procedure not reasoning by induction.

Principle of Mathematical Induction 1. You have a conjecture that you suspect is true for every positive integer. Prove that the conjecture is true for the case n = 1. 2. Show that if you assume the conjecture is true for some integer k, then the conjecture must also be true for the next number k+1 as well.

Notes:
1. The assumption that your conjecture is true for n = k is called the induction hypothesis.

2. Showing that the conjecture must be true for the next number k+1, is the rigorous check part of the principle.

3. Showing that the conjecture is true for n = 1 is the common starting point, but it is not the only way to start. You can start with any value of n and apply the two steps of the induction principle.

Why does the induction principle work? You have proved the conjecture is true for n = 1 (or whatever the first value is that you use). By showing step 2 of the induction principle, that is whenever the conjecture is true for some integer it must also be true for the next integer, you have established that the conjecture is true for n = 2 (or the first value + 1). Now since it holds for n = 2, by the proof given for step 2, it must hold for the next integer as well, so it holds for n = 3 (or the first value + 2). Continuing in this way you have an argument that the conjecture is true for all integers. (This suggestive argument can be made rigorous in a variety of ways, such as by the use of the well-ordering principle.)

The Tromino Puzzle: For a square grid 2ⁿ by 2ⁿ choose a single square. The rest of the grid can be tiled using trominoes, L-shaped tiles covering three squares each. (Click here for pictures of trominoes.)

Animation 1 shows the tiling on a 4 by 4 grid.

Animation 1.

Next we show how to apply the induction principle to prove the conjecture

For a square grid 2ⁿ by 2ⁿ choose a single square. The rest of the grid can be tiled using trominoes.

Case: n = 1 For a square of side length 2 using Figure 1 it follows that any placement of the single white tile permits completion of the tiling by a tromino. 

Figure 1.

Before proceeding to step 2 of the induction argument, let's experiment a bit more.

Case: n = 2 Consider a square of side length 4 which is 4 copies of a square of side length 2 as shown in Figure 2.

Figure 2.

Ideally we want to be able to prove that if we choose any of the 16 squares, the rest can be tiled by using trominoes. This would require 16 separate cases. Let's check a few of these to see if we are on the right track with our conjecture.

• One case is shown in Animation 1 above.

• A second case can be shown in an animation by clicking here.

• To check a few more cases click here to use an applet. Choose 4 for each side. You may need several tries to obtain a tiling!

• We can solve all the 16 cases. Thus we can say

For a square grid 2² by 2² choose a single square. The rest of the grid can be tiled using trominoes.

For a square with side length 4, the 16 cases can be done, but increasing the side length to be 2^k increases the number of cases dramatically so that this strategy of "checking" all the cases is not feasible. Let's see how to reformulate the rigorous check procedure to avoid checking the 16 cases individually.

Starting with the 4 by 4 square in Figure 2 choose a square to start with. It will be in one of the four 2 by 2 squares. For instance as in Figure 3. Next place a single tromino so that it occupies one square in each of the other three 2 by 2 squares; see Figure 4.

Figure 3.

Figure 4.

IMPORTANT OBSERVATION:

Now each of the four 2 by 2 squares has one square "occupied", so by the proof of the case for n = 1, it can be tiled using (only) trominoes. It then follows that 4 by 4 square can be tiled using (only) trominoes, once a single square has been chosen.

Thus we have proved the conjecture for the case n = 2 without considering all the cases individually. The observation above is the key to the proof of the general case, which we do next.

This more efficient approach suggests how to carry out the inductive process. We make the following induction hypothesis.

Given a positive integer k, assume that if a square grid 2^k by 2^k has one cell occupied by single square tile, then we can tile the rest of the grid using trominoes.

Let's see how we use the induction hypothesis to prove the conjecture for a square grid 2^k+1 by 2^k+1. We start by noting that the square grid 2^k+1 by 2^k+1 is made up of four 2^k by 2^k square grids as shown in Figure 5. We randomly choose a single starting square in one of the quadrants of Figure 5. We then place a single tromino so that it occupies one square in each of the other three quadrants as shown in Figure 6. Now each of the four 2^k by 2^k quadrants contains a single starting square.

Figure 5.

Figure 6.

Finally apply the induction hypothesis to each of the four 2^k by 2^k quadrants to conclude that

       For a square grid 2^k+1 by 2^k+1 choose a single
       square. The rest of the grid can be tiled using trominoes.  

The two steps of the principle of induction have been verified, so it follows that our conjecture is true for any 2ⁿ by 2ⁿ square.

       Auxiliary Resources:          

• Norton Starr at http://www.amherst.edu/~nstarr/puzzle.html has several applets where you can select the number of squares on a side and try your hand at tiling to solve the tromino puzzle.  In addition he provides a variety of information relating to this puzzle, especially where to get a "physical" version of the puzzle.

• At http://www.cut-the-knot.org/Curriculum/Games/TrominoPuzzle.shtml
  is a larger square to try your tiling skill.

• Another nice applet where you can choose the size of grid is at http://www.utc.edu/Faculty/Christopher-Mawata/trominos/

• For a list of Tromino Puzzle Print Resources and more Internet Sites compiled by Norton Starr click here.

References:

[1] B. Kolman and D. Hill, Student Solutions Manual for Elementary Linear Algebra, Seventh Edition, Prentice Hall, Upper Saddle River, New Jersey, 2000, page 21.