Let $T(m,n)$ for integers $m,n$ be the least number of integer-sided squares needed to tile an $m\times n$ rectangle. Clearly $T(kx,ky)\leq T(x,y)$. Are there integers $x,y,k\gt 1$, such that $T(kx,ky)
Minimum number of integer-sided squares needed to tile an $m$ by $n$ rectangle.
-
0Solutions up to 300×300 can be seen at [Minimally Squared Rectangles](http://demonstrations.wolfram.com/MinimallySquaredRectangles/) and [int-e.eu](http://int-e.eu/~bf3/squares/view.html#13,11). No counterexamples found yet. – 2013-04-03
3 Answers
$T(m,n)$ is tabulated at the OEIS. Also, several references are given:
Richard J. Kenyon, Tiling a rectangle with the fewest squares, Combin. Theory Ser. A 76 (1996), no. 2, 272-291.
Mark Walters, Rectangles as sums of squares, Discrete Math. 309 (2009), no. 9, 2913-2921.
Bertram Felgenhauer, Tiling rectangles by minimal number of squares.
Maybe you could have a look at those, to see whether your question is considered (and, if it is, you could then report back).
-
0No luck there.. – 2012-11-20
I've posted a 4944 possible counterexamples at Possible Counterexamples to the Minimal Squaring Conjecture. Odds are at least one of these is a valid counterexample.
Data and verified pictures up to 388 at Minimally Squared Rectangles
Other information at tiling a rectangle with the smallest number of squares
According to my notes there, my minimal possible counterexample is currently
-
3Yes, @EuYu. Rectangle $71 \times 81$ requires $10$ squares only. Edges (for example): $38$ (left-up), $43$(right-up), $33$(left-bottom), $28$(right-bottom), $20$(bottom), $8$, $8$, $5$, $4$ and $4$. – 2012-11-22
Here's the Bouwkamp code of two simple perfect squared rectangles:
- 13: 304x274 (141,78,85)(71,7)(92)(133,8)(51,28)(23,97)(74);
- 15: 152x137 (83,69)(31,38)(54,29)(16,15)(8,30)(25,4)(1,22)(21).
There is no lower-order simple squared rectangle of either size, but there might be compound ones. If not then T(304,274) = 13, T(152,137) = 15, and T(304,274) < T(152,137).
-
2The $152 \times 137$ rectangle can be subdivided into 12 squares with integer side lengths. http://pictat.com/show.php?i=/2012/11/29/43292squaredrec.png – 2012-11-29