3
$\begingroup$

This is a follow-up of my recent thread about tiling a $m\times n$ rectangle with squares:

I'm wondering to what extent a minimal tiling is essentially unique, that is, up to reflections of the whole rectangle or of (tiled) rectangles contained in it. I guess this definition is tantamount to saying that the collection of the square sides is unique.

First, let me suggest a more suitable definition of reducibility than in the other thread:

We'll call a rectangle (or a minimal tiling of it) reducible if it can be split into two (tiled) rectangles.

By playing around a bit with irreducible tilings, I have the impression that there are always some of the squares that form a smaller rectangle, but that apart from reflections inside of those smaller rectangle(s), such a tiling is unique.

Are all irreducible tilings essentially unique?

Do all minimal tilings contain a (tiled) rectangle?

The smallest irreducible rectangles are

$(13,11)\quad (17,16)\quad (19,16)\quad (19,17)\quad (19,18)\quad (20,17)\quad (21,19)\quad (25,23)\quad $ $ (26,22)\quad (27,23)\quad (27,25)\quad (28,27)\quad (29,25)\quad (29,27)\quad (31,23)\quad (31,25)\quad $ $ (31,26)\quad (31,27)\quad (31,28)\quad (31,29)\quad (31,30)\quad (32,27)\quad (32,29)\quad (32,31)\quad $ $ (33,26)\quad (33,28)\quad (34,25)\quad (34,32)\quad (35,31)\quad (35,34)\quad (36,31)\quad (37,29) $.

Now looking at reducible rectangles:

Note that a reducible rectangle can be splittable horizontally or vertically, often in several ways, and sometimes both at a time. For example, $f(15,8)=f(7,8)+f(8,8)=f(15,3)+f(15,5)$. So those tilings are far from unique. But now:

We'll call a rectangle (or a minimal tiling of it) coprime-reducible if the rectangle can be split into two (tiled) rectangles that have coprime sides each.

For a given $m\le 85$, the majority (in average about 90%) of the $m\times n $ rectangles with $n\lt m$ are reducible. But in the whole range, there is no rectangle that is coprime-reducible...

Is it possible to show that coprime-reducible rectangles don't exist?

EDIT: Note that as the values $f(m,n)$ for given m and for coprime $n$ between $m/2$ and $2m$ are seemingly very close to each other, the value of a coprime-reducible one in this range would have to be about the double of the others. This sort of rules out their existence heuristically.

Improve this question
$\endgroup$
1
  • $\begingroup$ I think it is feasible to do a near-brute force search on minimal square tilings for rectangles of small dimensions. Knowing that a tiling of O(log(pq)) exists for a p by q rectangle means a branch and bound algorithm can scan the possibilities pretty quickly to find all minimal tilings. Using theory to make good choices for p and q should allow a nice exploration, perhaps even for p into the thousands. Gerhard "Ask Me About System Design" Paseman, 2012.12.17 $\endgroup$
    – Gerhard Paseman
    Commented Dec 17, 2012 at 21:49

1 Answer 1

Reset to default
2
$\begingroup$

I just found that the answer to the first question about uniqueness is negative.

We have $f(34,29)=9$, and there are at least two essential different minimal tilings:

  • an irreducible one (squares of sides 19,15,14,10,10 clockwise and 4x1 in the middle)
  • a reducible one (squares of sides 17,17,12,12,6,4,4,4 clockwise and another one of side 6 in the middle)
Improve this answer
$\endgroup$

You must log in to answer this question.

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