Covering a square by small perimeter rectangles (Q1081125)

Given a partition of the unit square into n rectangles whose edges are parallel to the coordinate axes, we denote by p(n) the largest of their perimeters. The authors show that p(n) equals at least \(4(2m+1)/(n+m(m+1)),\) where m is the largest integer whose square does not exceed n: they define a linear program for p(n) and solve it by duality considerations, using the fact that the dual program only has three variables. An upper bound for p(n), as well as a discussion of several related questions, are included.