Minimum square partitions for 4x3 and 5x4 rectangles

Question

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):

Answer 1

The $4\times 3$ case can be proven similarly to the $3 \times 2$ case:

Consider the number of corners covered by each square in the partition. If each square covers at most 1 corner, then there must be at least 4 squares. Otherwise, if a square covers 2 corners, then its side length must be 3 and you get the same partition you already found. So you cannot have a partition of less than 4 squares.

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.
• Thus all 4 corner squares must have a side length of at most 2, hence their total area is at most 16, which is less than the total area of 20, so we need at least one more square.