Abstract:

We consider the problem of tiling large rectangles using smaller rectangles with the prescribed dimensions 4 x 6 and 5 x 7. Problem B3 on the 1991 William Lowell Putnam Examination asked "Does there exist a natural number L such that if m and n are integers greater than L, then an m x n rectangle may be expressed as a union of 4 x 6 and 5 x 7 rectangles, any two intersect at most along their boundaries?" Narayan and Schwenk showed in 2002 that all rectangles with length and width at least 34 can be partitioned into 4 x 6 and 5 x 7 rectangles. We investigate necessary and sufficient conditions for an m x n rectangle to be tiled with 4 x 6 and 5 x 7 rectangles. Ashley et al. answered this question for all but 37 cases. We use an integer linear programming approach to eliminate all but five of these cases. 