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.

$\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$ Dec 17, 2012 at 21:49

1 Answer 1

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)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.