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