Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

enter image description here

share|improve this question
    
There have been some discussions of tiling rectangles with squares at MathOverflow, e.g., mathoverflow.net/questions/116382/… –  Gerry Myerson Nov 10 '13 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. –  Realz Slaw Nov 10 '13 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. –  Gerry Myerson Nov 10 '13 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. –  Erel Segal Halevi Nov 17 '13 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. –  Realz Slaw Nov 17 '13 at 5:32
add comment

1 Answer 1

up vote 2 down vote accepted

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.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.