“A square can be tiled with n congruent 1 x 2 rectangles for any n except 1, 3 or 4.”
Tom Crawford proved this in the above Numberphile video, “A Problem with Rectangles”. I give an alternative proof that uses the following lemma.
Lemma: Every n ≥ 2 (except 3, 4 or 7) is the sum of 2, 5 or 6 non-zero squares.
Proof: Every n > 33 is the sum of 5 non-zero squares. The exceptions for n ≤ 33 are 1, 2, 3, 4, 6, 7, 9, 10, 12, 15, 18 and 33. This is proved here (which in turn uses Lagrange’s Four Square Theorem that any natural number is the sum of four integer squares). It is easily checked that 2 (1+1), 10 (1+9) and 18 (9+9) are the sum of 2 non-zero squares and that 6, 9, 12, 15 and 33 are the sum of 6 non-zero squares – can you work them out for yourself?
The title’s result for n equal to the sum of s = 2, 5 or 6 squares follows from first dividing a square into s rectangles and second subdividing each rectangle into a grid of 𝑘2 rectangles. (In this note all rectangles are congruent to a 1×2 rectangle.) The case of n = 7, as in Tom’s proof, is treated specially. Here are some examples showing the first division drawn with heavy lines, the second division drawn with lighter lines, and using random colours for each rectangle.
For example, in detail for n = 47 which is the sum of s = 5 squares: 52 + 42 + 22 + 12 + 12, first divide the square into 5 rectangles (each having the correct ratio), shown below. Then assign to the rectangles the square numbers – in any order:
Finally, subdivide each rectangle containing the square number 𝑘2 into a k x k grid of rectangles, as shown in colour above (middle diagram).
The special case of n = 7 can be solved by considering the necessary condition that 7 rectangles fit into a square of length 𝑙. That is, find integers 𝑎1, 𝑎2, … , 𝑎7 with 1 ≤ 𝑎1 ≤ 𝑎2 ≤ ⋯ ≤ 𝑎7 so that
(𝑎1 × 2𝑎1) + ⋯ + (𝑎7 × 2𝑎7) = 𝑙2
or, noting that 𝑙 must be even
𝑎12 + ⋯ + 𝑎72 = 𝑙2 / 2
By trial & error we find a solution for 𝑙 = 6 : 𝑎1 = 𝑎2 = 𝑎3 = 𝑎4 = 𝑎5 = 1, 𝑎6 = 2, 𝑎7 = 3 which yields Tom’s solution. A different solution is found for 𝑙 = 8 : 𝑎1 = 𝑎2 = 1, 𝑎3 = 𝑎4 = 𝑎5 = 2, 𝑎6 = 𝑎7 = 3, which yields: