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.

Improve this question
$\endgroup$
5
  • $\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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 10:30

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
6
  • $\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, 2013 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, 2013 at 18:45
  • $\begingroup$ @YuvalFilmus what about those specific rectangles I drew above? Are those minimally tiled? $\endgroup$
    – Realz Slaw
    Nov 9, 2013 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, 2013 at 23:57
  • $\begingroup$ @YuvalFilmus I asked this as a follow-up on math.SE. $\endgroup$
    – Realz Slaw
    Nov 10, 2013 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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