# What is the minimum square partition of an almost-square rectangle?

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:

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.

• Is it just me, or is ${\rm M{\small IN}S{\small QUARES}}(R_{w,h})=\frac {\max (w, h)}{\gcd (w, h)}$? – Karolis Juodelė Nov 8 '13 at 18:29
• @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}$. – Realz Slaw Nov 8 '13 at 20:21
• Right, I was silly. Still, the covering follows euclidean algorithm. The number of squares is the number of steps. I think... – Karolis Juodelė Nov 8 '13 at 21:07
• @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). – Realz Slaw Nov 8 '13 at 21:08
• Please format your questions with a lighter hand. Formatting should be functional in supporting the reader; you used a sledgehammer. – Raphael Nov 10 '13 at 10:30

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$).
• 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.) – Hendrik Jan Nov 9 '13 at 12:13
• Have a look at Kenyon's paper - it gives an algorithm which tiles a $w \times (w-1)$ rectangle with $O(\log w)$ squares. – Yuval Filmus Nov 9 '13 at 18:45