# Using your Head is Permitted

## March 2014 solution

We divide the problem into three cases. For each, we not only prove that
*m* is a perfect square but also give its exact value.
### Case 1: *n*<*k*

In this case, it is clear that not even a single *k*-by-1 tile can be
placed inside the *n*-by-*n* square. Hence,
*m*=*n*^{2} and is a perfect square.
Notably, this demonstrates the importance of the puzzle's specification that
each square of the *k*-by-1 tiles must align with a chessboard square.
Suppose, for example, *k*=5 and *n*=4, it is possible to place a
5-by-1 tile diagonally in a 4-by-4 square. This will leave 11 free squares,
which is not a perfect square.

#### Case 2: *n* mod *k* ≤ *k*/2

Let *r*=*n* mod *k*.
Tile the entire rectangle from position (*r*,0) to position
(*n*-1,*n*-1) by horizontal tiles, and the entire rectangle from
(0,*r*-1) to (*r*-1,*n*-1) by vertical
tiles. This leaves untiled the square between (0,0) and
(*r*-1,*r*-1). I claim that if we are able to tile the board, leaving
only a square of width at most *k*/2 untiled, then this is the optimal
tiling.

To prove this claim, let us color each of the chessboard's squares. We will
color (*x*,*y*) by a color corresponding to
(*x*+*y*) mod *k*. Note that in this coloring, every
*k*-by-1 tile covers exactly one square of each of the *k* colors.

Consider, however, the colors of the untiled *r*-by-*r* square. Its
(0,0) corner gets the 0 color, and the colors advance up until its
(*r*-1,*r*-1) color gets the color corresponding to
2*r*-2. This is, by assumption, smaller than *k*, so still unaffected
by the modulo. In fact, 2*r*-1 is also smaller than *k*, so the
entire untiled area does not include any square of the color corresponding to
2*r*-1.

We've demonstrated this for a square with one corner at (0,0), but the principle
is sound regardless of where the square is. If this is the only square left
untiled, this means that the number of *k*-by-1 tiles used was exactly
enough to exhaust all of the chessboard's squares colored by some specific
color. Therefore, no arrangement of the tiles can be made to use more
*k*-by-1 polyominoes. Therefore, *m*=*r*^{2} is the
optimum. Here, too, the optimum is a perfect square.

#### Case 3: *n* mod *k* > *k*/2

Once again, let *r*=*n* mod *k*.
We use the method of Case 2 to reduce to a
(*k*+*r*)-by-(*k*+*r*) square. Now, let us tile the
remaining square in the way demonstrated below.

The untiled portion left in the center has a square shape, and its width is
*k*-*r*<*k*-*k*/2=*k*/2. By the claim proved in
Case 2, this is, once again, the optimal tiling, leaving
*m*=(*k*-*r*)^{2} squares untiled. Once again, *m*
is a perfect square.

Q.E.D.

Back to riddle

Back to main page