Indirect Reasoning and the Chessboard

By Jonathan Osters, The Blake School

I have always been a fan of the movie The Prestige (https://www.youtube.com/watch?v=LV-cXixgrho). The opening scene of the movie shows how to do a good magic trick. I think that sometimes, good teaching is similar to the outline described in the movie. Dan Meyer uses three acts frequently, and this problem uses three variations of the same problem.

In class this week, we have been studying indirect proof, which is a very challenging topic for beginning Geometry students. We show that a situation must be true by eliminating the chance that it is false. To illustrate this idea, we explored a classic problem in mathematics involving a checkerboard. The framework of the problem is very simple: you have a standard 8×8 checkerboard, and dominoes that cover two squares each.

The Pledge

The first question I ask them is, can you tile the checkerboard with dominoes? It does not take long for the first students to show a solution, and I ask if there are other solutions. Below are several such solutions.

Tiling 1      Tiling 2     Tiling 3

You can see that there are a variety of different solutions to this problem. They all come to the conclusion that there are 32 dominoes to cover 64 squares, and that for the dominoes to cover the board, there must be an even number of squares.

The Turn

The second question I ask is: suppose the opposite corners of the checkerboard were cut away. Would it still be possible? Many emphatically express that it is, since there are still an even number of squares (62). I turn them loose to explore.

Chess 1

Some students insist, after failing the first time, that it can’t be done. I encourage them to continue trying; maybe they just haven’t found the solution yet! After attempting and failing numerous times, I call the class back together and ask if anyone came up with a solution. I contrast their early, frequent, and easy success with the current problem, and give them two choices: (1) A room full of intelligent, capable students failed to solve a solvable problem when they were able to solve a similar problem minutes ago, or (2) the problem is not actually solvable. Students become inclined to believe the latter, and I insist that if this is the case, then we should be able to explain why the problem is not solvable.

I have students generate a list of given information. There are only two main givens: first, is that each domino will cover two squares, and the other is that there are 62 squares. I remind them, only at this point, that the checkerboard has different colored squares, and ask if they can refine the givens with this new information. The given information is finally refined to: (1) each domino covers a white square and a black square, and (2) there are 32 white squares and 30 black squares on this board.

I then have them prove this checkerboard cannot be covered with dominoes.

Proof:

Assume that the board can be covered with dominoes. Since dominoes cover one black and one white square, n dominoes will cover n black and n white squares. This statement is a contradiction to the given information that there are more white squares than black. Therefore, this board cannot be covered with dominoes. QED

The Prestige

The key to the follow-up is to get the students to drive it with lots of “what if” questions. In class this week, I got the following “what if” questions as follow-up.

“What if you tried this on a 7×7 board, where the opposite corners are different colors?”

“What if, instead of removing a square from two corners, you added a square to two corners?”

“What if you removed a square from each corner instead of just two?”
“What if the squares you removed were different colors but not corner pieces?”

“Will you be able to cover the board if you remove ANY two squares, so long as they are different colors?”

These are absolutely wonderful questions, and get at the heart of what a true mathematician does. They are able to see that the first question, about the 7×7 board, does not work based on the odd number of squares. They come to realize that the adding of two squares creates a problem that reduces to the one we just solved, which is a mathematical technique that requires a very sharp mind.

The last question is the trickiest. It is the most general, to be sure. For instance, the scenario below is one such instance of removing two squares and being able to tile with dominoes.

Tiling 4

As to whether it is always possible to do? Well, I will tell you that my friend and I sat down and we have a proof as to whether or not it is always possible… but a magician never reveals all his secrets. [We will post the proof next week 🙂 ]

Leave a Reply

Your email address will not be published. Required fields are marked *