# primality on tiles?

Call $S_n$ the square of area $n^2$. See it as a collection of $n^2$ unit squares. In the following, what I call tile is a collection of unit squares that are glued together.

If $n$ is not prime, say $p \times q$, it is possible to tile $S_n$ with $n$ tiles that are rectangles whose sides are $1$ and $n$. It is also possible to tile $S_n$ with $n$ rectangles whose dimensions are $p$ and $q$.

So, when $n$ is not prime, there is not a unique way to tile $S_n$ with exactly $n$ tiles of the same shape.

For $n=2$, $3$ or $5$, easy computations show that the rectangle of dimensions $1$ and $n$ is the unique shape that tiles $S_n$ with $n$ elements. What about other primes?

I don't know if this question is well-known and/or has been studied. I have looked at several chapters of Martin Gardner's books but I did not found this one.

-
Are those $n$s in $S_n$ and the number os squares the same? If not, try changing one of them, this can be misleading. – Marra Sep 27 '12 at 11:50
The tiles you are talking about are called polyominoes. There is a lot of literature about them. I don't know whether the specific problem you ask about has been studied. – Gerry Myerson Sep 27 '12 at 12:40
Oh yes, I forgot the name, thanks! At the moment I don't know many things on them. Do you know if there is a place where all solved problems and references are listed? – Prénom Nom Sep 27 '12 at 12:45

The go-to book on this kind of problem is Polyominoes, by Solomon W Golomb. I have the 2nd edition, copyright 1994, so it's quite possible that there has been more recent work on this problem.

Chapter 8, starting on page 97, is about tiling rectangles. Following Klarner, Golomb defines the order of a polyomino $P$ as the minimum number of congruent copies of $P$ that can be assembled to form a rectangle. On page 97, Golomb writes, "there are no polyominoes of order 3" (he attributes the result to Ian Stewart). On page 100, he writes, "no polyomino whose order is an odd number greater than 1 has ever been found."

This is pretty far from answering the question. Golomb is tiling rectangles, you're asking for more since you want to tile a square. Golomb wants to tile the smallest rectangle, but you're asking for less, since you don't care if the polyomino tiles a smaller rectangle as long as it also tiles your square. But in most of the examples in the book, $n$-ominoes (that is, polyominoes of size $n$) of order $m$ have $n\lt m$, so they can't tile an $n\times n$ square.

EDIT: There is discussion of related problems at http://mathoverflow.net/questions/11753/cutting-a-rectangle-into-an-odd-number-of-congruent-pieces which includes results postdating the Golomb book.

-
Thanks a lot for all these results ! – Prénom Nom Sep 28 '12 at 20:05

Well, you want to partition $S_p$ for $p$ equal rectangles, right?

If equality is assumed (at least that of area), then it's easy: each rectangle has to have area $p^2/p=p$ so the rectangle (of integer sizes, of course) has to be $1\times p$.

-
Well, I want a tiling of $S_n$ with $n$ similar shapes, but they don't have to be rectangles. – Prénom Nom Sep 27 '12 at 12:30