University of Arizona
Institute for Mathematics and Education

The Tucson Teachers' Circle

Ji Li and Ginny Bohme presented Proof by Crayon

    for MEAD, January 30, 2010

5 by 5 grid.

Dr. Li began her talk by asking participants to tile a 4 by 4 grid with 1 by 2 dominoes. Tiling means to completely cover the board with dominoes so they do not overlap or extend past the edge of the board. Participants showed the different ways that the tiling could be completed.

Participants were then asked to tile the 4 by 4 grid with one square is missing. Participants quickly realized that it was impossible to tile, since each domino contains two squares, but the given grid contained an odd number of squares. So they were challenged to explore various configurations of 4 by 4 grids missing two squares, and record which arrangements can be tiled, and which cannot be.

8 by 8 grid.

One grid discussed was a 4 by 4 board with two opposite corners missing. We found that it could not be tiled. But how can we prove that? Dr. Li showed a proof by exhausting all possibilities of domino tiling within a couple of steps. This method is called the method of forcing, and is a legitimate method in formal mathematical proofs.

But what if we are given an 8 by 8 board with two opposite corners missing? Is there a domino tiling for this board? The forcing method may work, but that will take a lot longer. Dr. Li introduced the idea of coloring the board with alternate colors. If there exists a domino tiling, then each domino will cover exactly two squares, one color each. That means if a domino tiling of the grid is possible, then there must be the same number of squares with each color. This proves that there is no domino tiling for an
8 by 8 grid with two opposite corners missing.

Fibonacci. Rather than using two colors on tiles, mathematicians might use the numbers "0" and "1" to denote the two different parts of the tile. This gives essentially the same idea, but saves time in filling the grids.

Dr. Li extended the tiling process by asking, "How many different tilings are possible for a 2 by n grid?" Participants were encouraged to start with some smaller numbers for n, and look for patterns in their answers. Fibonacci numbers showed up. But why? Participants were led through a bijection between all tilings for 2 by 4 grid and all tilings for 2 by 3 and 2 by 2 grids and showed the relationship.

In the end, Dr. Li gave two other counting problems that led to Fibonacci numbers.
The idea of combinatorial bijection is the key idea connecting these different
interpretations of Fibonacci numbers.

MSgroups Ji