Filling rectangles with integersided 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(nm,m) ≤ 1 + max(nm,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 ≥ m^{2}
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/s_{1} + 1/s_{2} to the number of removed
squares, where s_{1} + s_{2} ≤ m are the
sizes of the first two squares covering the row. The
harmonicarithmetic mean inequality shows that
1/s_{1} + 1/s_{2} ≥ 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
kmth 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 ≥ m^{2} 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