Problem:
A rectangular piece of paper measures units by units. Several lines are drawn parallel to the edges of the paper. A rectangle determined by the intersections of some of these lines is called basic if
(i) all four sides of the rectangle are segments of drawn line segments, and
(ii) no segments of drawn lines lie inside the rectangle.
Given that the total length of all lines drawn is exactly units, let be the maximum possible number of basic rectangles determined. Find the remainder when is divided by .
Solution:
Let be the number of unit line segments and be the number of unit line segments. Then . Each pair of adjacent unit line segments and each pair of adjacent unit line segments determine one basic rectangle. Thus the number of basic rectangles determined is . To simplify the work, make the substitutions and . The problem is now to maximize subject to , where are integers. Solve the second equation for to obtain
and substitute into to obtain
The graph of this equation is a parabola with intercepts and . The vertex of the parabola is halfway between the intercepts, at . This is the point at which assumes its maximum. However, this corresponds to a nonintegral value of (and hence ). From both and are integers if and only if . The nearest such integer to is . Then , and this gives the maximal value for for which both and are integers. This maximal value for is , and the requested remainder is .
The problems on this page are the property of the MAA's American Mathematics Competitions