An Integer linear programming formulation for tiling large rectangles using 4 x 6 and 5 x 7 tiles

Show full item record

Title: An Integer linear programming formulation for tiling large rectangles using 4 x 6 and 5 x 7 tiles
Author: Dietert, Grant
Abstract: We consider the problem of tiling large rectangles using smaller rectangles with the prescribed dimensions 4 x 6 and 5 x 7. Problem B-3 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.
Record URI: http://hdl.handle.net/1850/12275
Date: 2010-05-27

Files in this item

Files Size Format View
GDietertThesis5-27-2010.pdf 1.145Mb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML


Advanced Search

Browse