Proving by tiling and cutting

Some facts can be shown just by placing, cutting and moving shapes. The four works here are all examples of that idea.

A damaged chessboard and dominoes (the site’s “Damaged Chessboard”)

Cut off two opposite corners of an 8×8 chessboard. Can the remaining 62 squares be covered exactly by 31 dominoes, each covering two squares? No. The reason is colour. Every domino covers one white and one black square. But opposite corners have the same colour, so what is left is 30 of one colour and 32 of the other. The program checked that this board has 30 white and 32 black squares, and that at most 30 dominoes fit, never 31 (domino-chessboard/engine.test.ts).

The puzzle is said to have been posed by the philosopher Max Black in a 1946 book and popularised by Martin Gardner in 1957. What if one white and one black square are removed? Gomory’s theorem says the rest can always be tiled. It carries Gomory’s name, but the proof is said to have appeared in print in Honsberger’s 1973 book. The program also checked, over every combination from 2×2 up to 8×8, that any “one white, one black” hole can be tiled, and that removing two squares of the same colour never can.

Tiling with L-shapes (the site’s “L-tromino Board”)

Now take a board of 2 to the power n by 2 to the power n and remove any one square. Can the rest be covered exactly by L-shaped pieces of three squares? Yes. Split the board into four quarters. The removed square lies in one of them. Put one L in the middle so that it covers one square in each of the other three quarters, and now every quarter is a board half the size with one square missing. Just repeat. This was written up by Solomon Golomb in 1954, and the damaged-chessboard problem is said to have been his starting point.

The program checked that on 2×2, 4×4, 8×8 and other boards, any single missing square can be tiled by this recipe. The numbers of L-pieces are 1 on 2×2, 5 on 4×4 and 21 on 8×8. It also checked that 4 to the power k minus 1 is divisible by 3 (for k from 1 to 12), which is why the pieces fit exactly (l-tromino-board/engine.test.ts).

Four pieces make a T (the site’s “T Puzzle”)

Four pieces form the shape of a T. It spread as an advertising giveaway around 1900. The oldest known example is said to be a medicine advertisement from 1898, though some sources name a tea advertisement from 1903 instead, so the facts are unclear. It is also said to have grown out of a cross puzzle. It looks easy, but many people take a long time to solve it.

The work’s T combines a bar 8 wide and 2 tall with a bar 5 tall and 2 wide, so its area is 8×2 + 2×5 = 26. The four pieces have areas 8, 8, 3 and 7, which also add up to 26. The program checked that in the answer the pieces sit inside the T without overlapping, that swapping the two trapezoids is also a correct answer, and that moving one piece breaks the solution (t-puzzle/engine.test.ts). Matching areas do not guarantee matching shapes. That is the fun of it.

Seeing the Pythagorean theorem by cutting (the site’s “Pythagoras Dissection”)

With a right triangle’s legs a and b and hypotenuse c, a² + b² = c². Look at it as a statement about area: cut the square on a and the square on b into pieces and rearrange them to fill the square on c exactly. In this work the square on b is cut into four congruent pieces, which together with the square on a fill the square on c. For a 3-4-5 triangle that is 9 + 16 = 25. The program checked that the piece areas add up to c², that the four pieces from the b-square are congruent with area b²/4 each, and that in the answer the c-square is filled with no gaps (pythagoras-dissection/engine.test.ts).

A name tied to proofs of this kind is Henry Perigal, a nineteenth-century Englishman who worked as a stockbroker among other jobs and pursued mathematics and astronomy as a hobby. His dissection diagram is said to be carved on his gravestone. We could not confirm when he first found it or whether it was the first dissection proof, so we do not say.

What they share

• Counting shows why not: if the whites and blacks do not match in number, no amount of shuffling will tile the board.
• Split, and return to the same problem: cutting into quarters gives smaller copies of the same problem.
• Matching area is not matching shape: equal total area does not tell you the pieces will fit; you have to try.

In all four, the numbers about boards and pieces are only those the program checked.