Yooklid

On Jan 11 I briefly introduced Polyominoes and posed some interesting problems to delight our readers. If you haven’t read the post introducing this fantastic topic, I highly encourage you to do so before proceeding to read the solutions to the puzzles presented in that post.

• In the first problem it was asked if a checkerboard has a pair of diagonally opposite corner squares deleted then would it be possible to cover this “mutilated” checkerboard with dominoes. Recall that a domino covers exactly 2 squares in the checkerboard. It turns out that the “mutilated” checkerboard cannot be covered with dominoes and the proof is oh so elegant! The standard checkerboard contains 64 alternating dark and light colored squares. On this board, each domino will cover one light square and one dark square. Thus n dominoes will cover n light squares and n dark squares. However, the defective board has 32 squares of one color and 30 squares of another color and thus cannot be covered by dominoes. How beautiful was that?

• In this second problem it was asked if the reader could show a construction where 21 right trominoes and 1 monomino covers an 8X8 checkerboard. Moreover, the reader was asked to prove the remarkable fact that no matter where a monomino is placed on the checkerboard, the remaining squares can always be covered with 21 right trominoes. I will furnish a proof of this fact thus simultaneously answering the question about constructing such a covering.  Below is an 8X8 board:

Consider the 2X2 section of this checkerboard. For the sake concreteness, let us pick the 2X2 area at the top left of the checkerboard above. Essentially this area is 2X2 checkerboard in itself. Notice that no matter where you place a monomino on this 2X2 board, you can cover the other 3 squares with a right tromino.

Next let us consider a 4X4 area of the board above. Divide it into quarters, each of which is a 2X2 board. Now consider the upper left 2X2 board. Clearly we can place a monomino and right tromino and cover this 2X2 area. Now considering the upper right 2X2 board, we can leave the lower left square empty and cover the other 3 squares with a right tromino. In the lower left 2X2 board, we can leave the upper right square empty and cover the other 3 squares with a right tromino. And finally, in the lower right 2X2 board, we can leave the upper left square empty and cover the other 3 squares with a right tromino. Notice that we left 3 squares blank and these 3 squares nicely congregate at the center of the 4X4 checkerboard and can be convered with a right tromino. Thus we have shown how to cover the 4X4 checkerboard with 1 monomino and 5 right trominoes! Ah, we are making some big progress!

It is now plain to see that 8X8 checkerboard can be divided into 4 quadrants of 4X4 boards and we can apply the same technique we used to cover the 4X4 board! In fact, by mathematical induction it is true that we can cover any (2^n)X(2^n) board, where n = 1, 2, 3, …, with 1 monomino and  several right trominoes only. At a later time I will write a post about mathematical induction as a way of proof.

These problems barely scratch the surface of the theory of Polyominoes. Stay tuned for more truly mind bending puzzles about the arrangement of these simple figures!