2
$\begingroup$

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

enter image description here

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$.

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .