Motivated by:
Tiling an orthogonal polygon with squares,
How to prove that the minimum square partition of a 3X2 rectangle has 3 squares,
Minimum square partitions for 4x3 and 5x4 rectangles,
What is the minimum square partition of an almost-square rectangle?.
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.
The $R_{w\times w-1}$ rectangles illustrated below are minimally-square-partitioned by $w$ squares. Proofs here: How to prove that the minimum square partition of a 3X2 rectangle has 3 squares and Minimum square partitions for 4x3 and 5x4 rectangles).
However, in general, a $R_{w\times w-1}$ rectangle can be partitioned into $\mathcal O(\log w)$ squares (see What is the minimum square partition of an almost-square rectangle?, and Minimum tiling of a rectangle by squares, which refer to a paper called Tiling a Rectangle with the Fewest Squares by Richard Kenyon.
My question:
What is the minimum $w$, such that a $w\times w-1$ rectangle, $R_{w\times w-1}$, can be minimally-square-partitioned into $f(w)$ squares, and $f(w)<w$.
By the proofs cited above, $w\geq 6$, and by Yuval's answer cited above, $w\leq 7$. So the only question is now whether a $6 \times 5$ rectangle can be covered with 5 squares. I think the answer is yes: it can be covered by three $2 \times 2$ squares and two $3 \times 3$ squares. So $w=6$.