10 - Problem F: Solution

Summary

We consider covering a p × p board with k triominoes and one monomino. If such a covering exists then 3k + 1 = p2, so that p is not a multiple of 3. Thus if p ≡ 0 (mod 3) then a covering does not exist.

Next, it is easy to see that if we can cover a p × p board with one monomino and k triominoes, then we can also cover a (p + 3) × (p + 3) board with one monomino and k + (2p + 3) triominoes. Indeed, we can cover a p × p corner of the board with the single monomino and k triominoes, and then we can cover the rest of the board using 2p + 3 more triominoes. As we can cover a 1 × 1 board (with one monomino and no triominoes), it follows that we can cover a p × p boardwhenever p ≡ 1 (mod 3).

The remaining case is when p ≡ 2 (mod 3). Clearly, we cannot cover a 2 × 2 board. We ask the reader to show that it is possible to cover a 5 × 5 board with one monomino and eight triominoes.We have now solved our problem, which we record as a theorem.

Theorem A p × p board can be covered with one monomino and some triominoes if and only if p = 2 and p is not a multiple of 3.

While the solution given above is elementary, it does not give us any extra information, and it does not easily generalise. In general, the simpler the solution, the less information it gives!We shall now give an alternative discussion which yields much more information.

First, we attach to each square of the board a label x^ay^b. The values of a and b are 0, 1, … , p − 1, and the labels are attached in the natural way so that the bottom row has labels (from left to right) x⁰y⁰, x¹y⁰, … , x^p−1y⁰, and the top row has labels (from left to right) x⁰y^p−1, x¹y^p−1`, … , x^p−1y^p−1.