31
$\begingroup$

We are interested in tiling a rectangle with copies of a single tile (rotations and reflections are allowed). This is very easy to do, by cutting the rectangle into smaller rectangles.

What happens when we ask that the pieces be non-rectangular?

For an even number of pieces, this is easy again (cut it into rectangles, and then cut every rectangle in two through its diagonal. Other tilings are also easy to find).

The interesting (and difficult) case is tiling with an odd number of non-rectangular pieces.

Some questions:

  • Can you give examples of such tilings?
  • What is the smallest (odd) number of pieces for which it is possible?
  • Is it possible for every number of pieces? (e.g., with five)

There are two main versions of the problem: the polyomino case (when the tiles are made of unit squares), and the general case (when the tiles can have any shape). The answers to the above questions might be different in each case.

It seems that it is impossible to do with three pieces (I have some kind of proof), and the smallest number of pieces I could get is $15$, as shown above:

    alt text (source)

This problem is very useful for spending time when attending some boring talk, etc.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Obviously this question's been around for over 7 years, so I guess any confusion that was going to result already has, but it might be worth putting the crucial condition 'non-rectangular' in the title. $\endgroup$
    – LSpice
    Commented Sep 25, 2017 at 22:54

3 Answers 3

Reset to default
27
$\begingroup$

Golomb's book Polyominoes has a section on this. Call the smallest odd number of copies of a polyomino that can tile a rectangle its "odd-order". Then Golomb says there are polyominoes of odd order 1, 11, and 15+6t for all $t \ge 0$. The polyomino of odd order 11 is due to Klarner [1], and is illustrated here by Michael Reid.

Reid has lots of pictures of tilings of rectangles with polyominoes. In particular the 15+6t family can be seen: here are polyominoes with odd-order 15, odd-order 21, odd-order 27, and so on. Reid has shown [3] that other odd orders exist, including 35, 49, and 221, but I don't know if there's a general pattern.

Finally, Stewart and Wormstein [2] proved that polyominoes of order 3 do not exist. (Stewart's book Another Fine Math You've got Me Into suggests that Wormstein is a fictional character.)

[1] David A. Klarner, Packing a rectangle with congruent N-ominoes, J. Combin. Theory 7 (1969) 107-115, [2] Stewart, Ian N. and Wormstein, Albert. Polyominoes of order 3 do not exist. J. Combin. Theory Series A 61 (1992) 130-136.
[3] Michael Reid. Tiling Rectangles and Half Strips with Congruent Polyominoes. J. Combin. Theory Series A 80 (1997) 106-123.

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ Thanks for these very useful references. The "record" dropped from 15 to 11 pieces. Questions that remain: - is it possible with 5, 7, 9, or 11 pieces? - what about arbitrary shapes of pieces? I'm happy to see that the "kind of proof" I have is very similar to the one found in your ref [2]. (Anyone interested in one of the articles can ask me in private because the articles are unfortunately not available online, but greedily hidden to the public.) $\endgroup$
    – subshift
    Commented Jan 14, 2010 at 22:22
  • 1
    $\begingroup$ what about square? $\endgroup$
    – Anton Petrunin
    Commented Jan 15, 2010 at 1:31
  • $\begingroup$ Anton, could you be more specific? $\endgroup$
    – Michael Lugo
    Commented Jan 15, 2010 at 1:34
  • $\begingroup$ @Michael, Sorry, my first impression was that it is harder to tile a square. Now I see that even the example above produce a tiling of square (once you shrink it along X-axis). Still, if one makes it more restrictive; say that if one shrink along X-axis then tiles become non-congruent --- then I do not see an example... $\endgroup$
    – Anton Petrunin
    Commented Jan 15, 2010 at 19:24
  • 1
    $\begingroup$ More on Wormstein's fictionality is at this 2013 question: math.stackexchange.com/questions/448078/who-is-albert-wormstein $\endgroup$
    – Michael Lugo
    Commented Jan 3, 2017 at 14:33
15
$\begingroup$

I am posting the 11 pieces solution shown in the article cited by Michael (it is not freely available online).

    alt text (source)

This is the smallest known number of pieces. Some remarks:

  • The question is open for 5, 7, or 9 pieces. Get your pencils!
  • Everything so far is with polyominoes. Any suggestion with more complicated shapes?
  • Unlike the other solution I posted, this one cannot be resized along the $x$ or $y$ axis.
Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Note that this solution yields an answer with $2k + 11$ pieces, for all $k \geq 0$. $\endgroup$
    – subshift
    Commented Mar 4, 2010 at 9:30
  • 2
    $\begingroup$ Exhaustive search for non-rectangular n-ominoes n<=13 turned up no k-tile rectangles for k in [5,7,9]. Before I continue onward and upward, I should probably cull poor candidates before starting the Dancing Links routine. I'm already eliminating tiles with the wrong checkerboard parity (abs(white-black)>1), but are there any other quick tests I should be doing? NOTE: this posted prematurely...there are still a few 13-ominos left... $\endgroup$
    – Zomulgustar
    Commented Apr 27, 2016 at 15:36
9
$\begingroup$

Ok. It's easy to see that rectangle cannot be cut into odd number of equal triangles: Monsky proved [here] that a square cannot be cut into an odd number of triangles with equal areas. But if we have rectangle divided into odd number of equal triangles, we could shrink it in one direction and get a square divided into an odd number of triangles with equal areas - contradiction.

Update: If the tile could be cut into odd number of triangles with the same area, then obvious that rectangle cannot be cut into odd number of such tiles. Example:

tile

Improve this answer
$\endgroup$
9
  • $\begingroup$ the rectangle -> square reduction is not valid. to tile, at least two triangles must have a different orientation. but this means the 'stretching' turns them into two different triangles, ie they are not copies/tiles. $\endgroup$
    – Matus Telgarsky
    Commented Jan 14, 2010 at 15:02
  • 2
    $\begingroup$ Yes, but the areas of triangles remain equal. Monsky's theorem is valid for all tilings into triangles with equal areas. $\endgroup$
    – Nurdin Takenov
    Commented Jan 14, 2010 at 15:08
  • $\begingroup$ oops! anyway, that is cool. $\endgroup$
    – Matus Telgarsky
    Commented Jan 14, 2010 at 15:12
  • 6
    $\begingroup$ Monsky's proof involves a rather nice and surprising application of the 2-adic numbers in combinatorial geometry. I'd recommend the entertaining writeup of it by Sherman Stein in The Mathematical Intelligencer 26 (2004). $\endgroup$
    – dke
    Commented Jan 14, 2010 at 15:42
  • 2
    $\begingroup$ Do you know if there is a tiling of a rectangle into an odd number of congruent convex $n$-gons for $n\geq 5?$ $\endgroup$
    – Victor Protsak
    Commented Jul 27, 2010 at 21:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .