# Minimum number of integer-sided squares needed to tile an $m$ by $n$ rectangle.

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)<T(x,y)$?

-
For some references and perhaps some computational ideas: oeis.org/A219158 – Matthew Conroy Nov 19 '12 at 3:00
Of course not. (Waves hands and ducks) Maybe you can use some of the ideas in Fourteen proofs of a result about tiling a rectangle-Wagon to prove this. – Ross Millikan Nov 19 '12 at 3:10
mathoverflow.net/questions/113899/… – fff Nov 21 '12 at 9:06
Solutions up to 300×300 can be seen at Minimally Squared Rectangles and int-e.eu. No counterexamples found yet. – Ed Pegg Apr 3 '13 at 13:45

$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).

-
No luck there.. – fff Nov 20 '12 at 3:06

A 162*142 rectangle can be tiled with 12 squares. Bouwkamp code: 12 162 142 (83,79)(4,12,63)(59,19,9)(1,11)(10)(40)

See at Squaring.net

An 81*71 rectangle seems to require 20 squares for a non-greedy tiling (with the following code). With a greedy method, 19 squares are needed.

20 81 71 43 38 13 9 16 28 15 4 5 9 8 3 2 1 17 4 13 2 12 11

-
It seems that $81 \times 71$ only needs $10$ squares so the $12$ square tiling for the larger rectangle is not optimal. This link lists the minimal numbers for the tilings. $81 \times 71$ is entry $3311$. The list is a continuation of A219158. – EuYu Nov 21 '12 at 22:39
Yes, @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$. – Oleg567 Nov 22 '12 at 5:12

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).

-
There is no restriction to distinct squares. – Gerry Myerson Nov 29 '12 at 1:03
The $152 \times 137$ rectangle can be subdivided into 12 squares with integer side lengths. pictat.com/show.php?i=/2012/11/29/43292squaredrec.png – Dave Radcliffe Nov 29 '12 at 3:30