Yooklid

In this post I will briefly introduce the fascinating subject of Polyominoes and pose some elementary problems that are sure to puzzle the incredible pattern matching machines in your skulls. Those of you who are familiar with Polyominoes might know that they inspired the very popular video game Tetris.

Polyominoes are shapes made by connecting certain number of equal-sized squares, each joined together with at least one other square along an edge. To make the definition clear, here are some examples of simple polyominoes composed of fewer than 5 connected squares:

From the figure above, you can see that a Monomino is composed of a single square and it is clear that there is just one such shape. A Domino is made of 2 connected squares and has only one shape, a rectangle. A Tromino is made of 3 connected squares and the figure above shows that there are only 2 distinct trominoes (straight tromino and right tromino) if we discount rotations and reflections. Similarly, a Tetromino is composed of 4 connected squares and there are 5 distinct tetromino shapes (straight, square, T, L and skew tetrominoes). The most popular type of polyomino that has inspired many games and puzzles are the 12 distinct Pentominoes:

Simple looking critters aren’t they? Simple as they might look, these shapes can be mixed together to form patterns and tessellations that are anything but simple. Polyomino patterns are actually examples of Combinatorial Geometry, that branch of Mathematics dealing with the ways in which geometrical shapes can be combined.

So that is it for this lecture on these simple looking shapes we call Polyominoes. For now! Let’s roll up our sleeves and get into some interesting problems in Combinatorial Geometry shall we?

• The first problem, with which some readers may be familiar, concerns dominoes: Given a checkerboard with a pair of diagonally opposite corner squares deleted (see figure below) and a box of dominoes, each of which covers exactly 2 squares, is it possible to cover this board completely with dominoes (allowing no vacant squares and no overlaps)? Explain your answer.

• It is impossible to cover an 8X8 board entirely with trominoes because 64 is not divisible by 3. However, it is a well known fact that the 8X8 board can be covered with 21 right trominoes and 1 monomino. Can you come up with a construction? What is more remarkable is that it can be proved that no matter where on the checkerboard a monomino is placed, the remaining squares always can be covered with 21 right trominoes. Can you come up with a proof? I realize that submitting a solution to this problem via the comments section would be problematic due to the geometric nature of the solution but I highly encourage you to try your hand at this remarkable problem. I know this is a stretch, but for those of you who would like to submit your geometric solution, you can email a file (an image or some other type of document) containing your geometric solution to yooklidean@gmail.com.

I will post the solution to these puzzles on thursday, 01/14/2010. Until then, happy pattern matching!

UPDATE:

[SOLUTION]

References

1. Golomb W., Solomon. Polyominoes.