# 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

• If n = m then h(n,m) = 1 ≤ max(n,m)
• If n > m, then h(n,m) ≤ 1 + h(n-m,m) ≤ 1 + max(n-m,m) ≤ max(n,m). The first inequality corresponds to cutting off an m×m square.
• The case that n < m is analogous to n > m.

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

• At least 4k squares are removed. To see why, note that we can account for the squares by adding 1/s for each row that the square overlaps with, where s is the size of the square. Because every row overlaps with at least two squares (otherwise an m×m square would be used), every removed row contributes at least 1/s1 + 1/s2 to the number of removed squares, where s1 + s2 ≤ m are the sizes of the first two squares covering the row. The harmonic-arithmetic mean inequality shows that 1/s1 + 1/s2 ≥ 4/m. Multiplying by the total number of rows removed, km, the claim follows.
• Covering the first km rows requires k squares. Obvious.
• The remaining space can be covered using at most m squares. Note that the gaps result from squares that overlap with the km-th row, where each square contributes a rectangle to the gap (possibly of width 0) whose width is smaller than its height. Therefore, using h(n,m) ≤ max(n,m), we find that the number of squares required to fill the gaps is bounded by the total height of the squares, i.e., m.

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