5
$\begingroup$

This question is motivated by an older question about tiling an orthogonal polygon with squares. It is a generalisation of my former question about how to prove that the minimum square partition of a 3X2 rectangle has 3 squares).

Let:

  • An almost-square-rectangle be a rectangle that has a width $w$ and height $h=w-1$.
  • A square partitioning be a covering by non-overlapping squares; the entire rectangle must be covered, all the squares must be disjoint.
  • A minimum-square-partitioning be a square partitioning, for which is no square partitioning that is made of a lesser number of squares.

Illustration:

enter image description here

Top row: The almost-square-rectangles of widths $3$, $4$ and $5$. Bottom row: Are these miminum-square-partitions of their corresponding rectangles?

My question is now:

What is the minimum-square-partitioning of an almost-square-rectangle?

Can we prove ${\rm M{\small IN}S{\small QUARES}}(R_{w,h=w-1})=w$?

Note a follow-up question, Minimum square partitions for 4x3 and 5x4 rectangles.

$\endgroup$
  • $\begingroup$ Is it just me, or is ${\rm M{\small IN}S{\small QUARES}}(R_{w,h})=\frac {\max (w, h)}{\gcd (w, h)}$? $\endgroup$ – Karolis Juodelė Nov 8 '13 at 18:29
  • $\begingroup$ @KarolisJuodelė with $R_{5,3}$ that gives me $5$, but I think you can cover a $R_{5,3}$ with a $1\cdot R_{3,3} + 1\cdot R_{2,2} + 2\cdot R_{1,1} = 4\text{ squares}$. $\endgroup$ – Realz Slaw Nov 8 '13 at 20:21
  • $\begingroup$ Right, I was silly. Still, the covering follows euclidean algorithm. The number of squares is the number of steps. I think... $\endgroup$ – Karolis Juodelė Nov 8 '13 at 21:07
  • $\begingroup$ @KarolisJuodelė yeah I agree it is related to what I intuitively know is the minimum-square-partition; with some thought one can come up with a formula for general $R_{w,h}$. I don't just want a general formula; I want a proof (a proof along with a general formula would be nice though). $\endgroup$ – Realz Slaw Nov 8 '13 at 21:08
  • $\begingroup$ Please format your questions with a lighter hand. Formatting should be functional in supporting the reader; you used a sledgehammer. $\endgroup$ – Raphael Nov 10 '13 at 10:30
6
$\begingroup$

A similar question was asked on Mathoverflow. The commenters mentioned a paper of Kenyon, which shows that the minimum number of squares required to tile a $w \times (w-1)$ rectangle is $\Theta(\log w)$. See also a related paper of Walters.


You can tile a $(4t+7) \times (4t+6)$ rectangle using only $t+5$ squares (for $t \geq 0$).

Tiling a 6 by 7 rectangleTiling a 10 by 11 rectangle Tiling a 14 by 15 rectangleTiling a 18 by 19 rectangle

$\endgroup$
  • $\begingroup$ Nice! Do I see room for recursion here? In the bottom right corner there is a $(2t+4)\times (2t+2)$ rectangle tiled with $t+2$ squares, in a way similar to the original solution, but scaled to a $2 \times 2$ grid. (sorry hard to express what I mean.) $\endgroup$ – Hendrik Jan Nov 9 '13 at 12:13
  • $\begingroup$ Have a look at Kenyon's paper - it gives an algorithm which tiles a $w \times (w-1)$ rectangle with $O(\log w)$ squares. $\endgroup$ – Yuval Filmus Nov 9 '13 at 18:45
  • $\begingroup$ @YuvalFilmus what about those specific rectangles I drew above? Are those minimally tiled? $\endgroup$ – Realz Slaw Nov 9 '13 at 22:50
  • $\begingroup$ That's probable, and should be provable using some case analysis. For more sophisticated methods, see Kenyon's paper, which uses the electrical resistance method. $\endgroup$ – Yuval Filmus Nov 9 '13 at 23:57
  • $\begingroup$ @YuvalFilmus I asked this as a follow-up on math.SE. $\endgroup$ – Realz Slaw Nov 10 '13 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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