Filling rectangles with integer-sided squares

Back to main page

Proofs

1. h(n,m) ≤ max(n,m)

This follows easily by induction on max(n,m), using a greedy algorithm. To wit, we have

2. h(n+m,m) = 1 + h(n,m) for 1 ≤ m ≤ 4

This follows from 3. (below) and inspection of known results. Because m is small, these equalities can also easily be proven by considering various possibilities of filling a strip of height m with squares.

3. h(n+m,m) = 1 + h(n,m) if 3n ≥ m2

Obviously, h(n+m,m) ≤ 1 + h(n,m), because any tiling of an n×m rectangle can be extended to a tiling of an (n+m)×m rectangle by adding an m×m square at one end. Note further that if we have an optimal tiling of an (n+m)×m rectangle that uses an m×m square, then we can move that square all the way to the left, implying h(n,m) ≤ h(n+m,m) - 1. Therefore, h(n+m,m) = 1 + h(n,m) follows in that case.

So assume that h(n+m,m) ≤ h(n,m). As we have just seen this implies that there is no optimal tiling of the (n+m)×m rectangle using an m×m square. Fix an arbitrary optimal tiling of the (n+m)×m rectangle. Let k = ⌊(n+m)/m⌋. The idea is to remove all squares overlapping with the first km rows of the rectangle, add k m×m squares instead, and then fill the remaining space. We have to account for squares removed and added.

Now if 3n ≥ m2 then 4k > k + 3n/m ≥ k + m, i.e., our new tiling uses fewer squares than our fixed tiling, contradicting its assumed optimality. Therefore, h(n+m,m) = h(n,m)+1 follows.

4. h(13,11) cannot be obtained by subdivision into rectangles

This follows by inspection of the result tables.

Back to main page

Valid XHTML 1.0 Strict