PROBLEM OF THE MONTH

SOLUTION

November, 2003





Jonathan Inbal provided the following solution:

THEOREM:An n x n square can be cut into "T" tetraminos if and only if n is divisible by 4.

In particular, a 10 x 10 square cannot be cut into "T" tetraminos.

PROOF: First, notice that a 4 x 4 square can be made out of "T" tetraminos as follows:

Therefore, if n is divisible by four the square can first be cut into 4 x 4 squares, each of which can be cut into four tetraminos.

Conversely, assume that the square can be cut into "T" tetraminos. Since each tetramino consists of 4 squares, the square must be cut into n2/4 tetraminos. Since this number must be an integer, n2 is divisible by four which implies that n is divisible by 2. Now, color the squares black and white in a checkerboard pattern

and notice that each tetramino will consist either of (a) three white squares and one black square or (b) three black squares and one white square. We now count the number of white squares in two different ways.
  1. Since n is even, exactly half of the squares are black and half are white. Therefore there are n2/2 white squares.
  2. Let w be the number of tetraminos composed of three white squares and one black square. The number of tetraminos composed of three black squares and one white square is n2/4 - w, so there are a total of 3*w + 1*(n2/4 - w) white squares.
Equating these two counts and solving for w, we get: w = n2/8. Since w is an integer, this equation implies that n2 is divisible by 8, which means that n must be divisible by 4.

This proof can be modified to provide some information in the case of an m x n rectangle. It can be shown that a necessary condition for the rectangle to be cut into "T" tetraminos is that the area, mn, must be divisible by 8. However, this condition is not sufficient, since a 1 x 8 rectangle can clearly not be subdivided. A sufficient condition is that both m and n be divisible by 4. Mr. Inbal has conjectured that this condition is also necessary. It would be interesting to try to prove his conjecture.