tiling a rectangle with squares: how unique are the minimal solutions? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T05:37:44Z http://mathoverflow.net/feeds/question/116641 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/116641/tiling-a-rectangle-with-squares-how-unique-are-the-minimal-solutions tiling a rectangle with squares: how unique are the minimal solutions? Wolfgang 2012-12-17T20:09:25Z 2013-01-05T10:22:00Z <p>This is a follow-up of <a href="http://mathoverflow.net/questions/116382/tiling-a-rectangle-with-the-smallest-number-of-squares" rel="nofollow">my recent thread</a> about tiling a $m\times n$ rectangle with squares:</p> <p>I'm wondering to what extent a minimal tiling is <em>essentially unique</em>, 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.</p> <p>First, let me suggest a more suitable definition of reducibility than in the other thread:</p> <blockquote> <p>We'll call a rectangle (or a minimal tiling of it) <em>reducible</em> if it can be split into two (tiled) rectangles. </p> </blockquote> <p>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. </p> <blockquote> <p>Are all irreducible tilings essentially unique?</p> <p>Do all minimal tilings contain a (tiled) rectangle?</p> </blockquote> <p>The smallest irreducible rectangles are </p> <p>$(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)$.</p> <p><strong>Now looking at <em>reducible rectangles</em>:</strong></p> <p>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:</p> <blockquote> <p>We'll call a rectangle (or a minimal tiling of it) <em>coprime-reducible</em> if the rectangle can be split into two (tiled) rectangles that have coprime sides each. </p> </blockquote> <p>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 <strong>no</strong> rectangle that is coprime-reducible...</p> <blockquote> <p>Is it possible to show that coprime-reducible rectangles don't exist? </p> </blockquote> <p>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.</p> http://mathoverflow.net/questions/116641/tiling-a-rectangle-with-squares-how-unique-are-the-minimal-solutions/116977#116977 Answer by Wolfgang for tiling a rectangle with squares: how unique are the minimal solutions? Wolfgang 2012-12-21T15:20:36Z 2012-12-22T10:12:29Z <p>I just found that the answer to the first question about uniqueness is <strong>negative</strong>.</p> <blockquote> <p>We have $f(34,29)=9$, and there are at least two essential different minimal tilings:</p> <ul> <li>an irreducible one (squares of sides 19,15,14,10,10 clockwise and 4x1 in the middle)</li> <li>a reducible one (squares of sides 17,17,12,12,6,4,4,4 clockwise and another one of side 6 in the middle)</li> </ul> </blockquote>