# Minimum square partitions for 4x3 and 5x4 rectangles

Motivation: Tiling an orthogonal polygon with squares

Followup question: What is the first $w$ such that a rectangle, $R_{w\times w−1}$ is minimally-square-partitioned by less than $w$ squares.. Yes, it only gets harder :D

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.

In my answer to the motivating question, I use several gadgets to construct a reduction from $\text{Planar-}3\text{-SAT}$. I assumed the minimum-square-partion of these gadgets to be the smallest I could find; but I am not satisfied with this, I want proof. So I began with the simplest: How to prove that the minimum square partition of a 3X2 rectangle has 3 squares. I then moved on to generalize it to What is the minimum square partition of an “almost-square-rectangle”?, and found my intuition to be wrong for the general case. So now I am a bit worried, are the following square partitions indeed minimum for their corresponding rectangles? I can't find any lesser square partitions, but I can't prove it either (except for the $3\times 2$ case):

• There have been some discussions of tiling rectangles with squares at MathOverflow, e.g., mathoverflow.net/questions/116382/… Nov 10, 2013 at 8:55
• @GerryMyerson that particular is definitely related. The differences: the question is discussing tiling with squares of integer size. I am concerned about squares in general. On the other hand, that question is more general, asking about all rectangles, I am concerned with only the $3$ pictured (of course some sort of algorithm/proof for the general case would be nice, but that question doesn't even have dice for integer-sized squares ...). I want a proof that these are the minimum-square-partitions, for all possible square-partitions, integer-sized or not. Nov 10, 2013 at 9:03
• You could look at all ways of cutting a rectangle into 3 squares, and show that no matter how you assign edge lengths to the squares, you never get a $3\times4$ rectangle; similarly, that no way of cutting a rectangle into 4 squares gives a $4\times5$ rectangle. Nov 10, 2013 at 9:11
• I managed to prove this by exhaustively checking all ways to cover the corners. This apparently becomes more complicated as the rectangle grows. Nov 17, 2013 at 5:30
• @ErelSegalHalevi it isn't true for some sizes of rectangles (see Yuval's answer), so obviously it has to grow harder :D I wonder what the limit of this is though; where it a $R_{w,w-1}$ rectangle becomes better covered than by $w$ squares. Nov 17, 2013 at 5:32

The $4\times 3$ case can be proven similarly to the $3 \times 2$ case:
The $5\times 4$ case can be proven similarly by considering the squares that cover the corners:
• If one of them has a side length of 4, then we are left with a row of $1\times 4$ that we must fill using the 5-sized tiling you already have.
• If one of them has a side length of 3, then we are left with a row of $1\times 3$ that we must fill with 3 small squares, and a rectangle of $2\times 4$ that we can fill with at least 2 squares, for a total of 6.