Can we find N such that all m x n rectangles with m, n > N can be tiled with 4 x 6 and 5 x 7 rectangles?
Solution
Answer: yes.
Moderately easy.
If a and b are relatively prime then we can express any integer N > ab as N = ra + sb with r and s positive integers. For a proof, take a > b, and observe that N, N - b, N - 2b, N - (a - 1)b are all positive and incongruent mod a, so they must constitute a complete set of residues mod a. In particular, we can find one which is congruent to zero mod a.
We can tile 35 x 5 and 35 x 7 using just 5 x 7 rectangles. But 5 and 7 are relatively prime, so we can use 35 x 5 and 35 x 7 rectangles to tile any 35 x n rectangle for n > 35. Similarly, we can tile 24 x 4 and 24 x 6 using just 4 x 6 rectangles. 4 and 6 have greatest common divisor 2, so we can use 24 x 4 and 24 x 6 rectangles to tile any 24 x 2n rectangle for n > 24. But 24 and 35 are relatively prime so for any 2n > 48, and m > 840 we can use 35 x 2n and 24 x 2n rectangles to tile an m x 2n rectangle. Finally, given any m x (2n+1) rectangle with 2n+1 > 83 and m > 840, we can divide it into an m x 35 rectangle and an m x 2n rectangle, each of which can be tiled. So any m x n rectangle can be tiled provided m, n > 840.
© John Scholes
jscholes@kalva.demon.co.uk
24 Sep 1999