Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

3 Answers 3

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

share|improve this answer
    
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

share|improve this answer
3  
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
3  
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).

share|improve this answer
2  
There is no restriction to distinct squares. –  Gerry Myerson Nov 29 '12 at 1:03
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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