The "mutilated chessboard" and end of class

Well, it's that time of year again; a bunch of final assignments due in the last week and exams on the horizon. I've enjoyed 236 quite a bit, and felt it introduced me to quite a few new and interesting concepts. I also appreciated Dan's enthusiasm throughout the course and willingness to help.

Anyways, after deliberating over what type of induction problem I found tricky throughout the course, I decided to write up the following one. Although once you understand the creative step in this problem it is quite simple, if you don't make the connection it is extremely difficult to formalize! These are the most interesting (and sometimes difficult) problems in my opinion; ones that require a non-obvious creative leap.

Prove by induction that a chessboard of any size (n x n), of at least size 2 x 2, with two black corners removed from it which are diagonal from each other, cannot be completed covered by a number of dominoes (each taking up two squares) equal to the total remaining squares on the board divided by 2.

Above, we see a diagram of the board for the typical 8x8 case and a representation of a domino below it.

Base case: n=2. Then, we would have one domino, and the board consists of two tiles diagonal from each other (i.e., no tiles which share an edge). Thus, it is clearly impossible to cover the board in this case.

Induction step: n>2. Assume that, for some j, the proposition to be proved holds. We want to show that it also holds for j+1. We notice that for a j x j board, there will be floor(j²/2) white tiles and ceil(j²/2)-2 black tiles. Thus, for a j+1 x j+1 board, there will be floor(j+1²/2) white tiles and ceil(j+1²/2)-2 black tiles. We can subtract the two values to see a pattern at each step. Specifically, the difference in either the black or the white tiles increases by 2 each time, but which one increases by 2 alternates at each step. Importantly, though, the white tiles are always increased by an even amount and the black by an odd amount. Thus, it follows that there are never the same amount of black tiles and white tiles added.

Since a domino must span 2 squares, it must be covering both a white tile and black tile. Since there are not an equal number of black tiles and white tiles, it is impossible to cover the added tiles with dominoes. And since it is also impossible to cover the tiles that were already there by the induction hypothesis, it is impossible to cover a j+1 x j+1 board with dominoes.

Conclude, by mathematical induction, that the proposition holds.

And that's that. Without noticing the trick with the tile colours, the proof is very tricky. In fact, the observation can be applied without using the inductive framework, but this was noticed only after attempting to use induction.

Anyways, have a great holiday everyone, and good luck on exams!