Maximum Basic Rectangles
A rectangular piece of paper measures 4 units by 5 units. Several lines are drawn parallel to the edges of the paper, going from one edge to the other. 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 2007 units, let $ N $ be the maximum possible number of basic rectangles determined. Find $ N $.
- 1
- 2
- 3
- +
- 4
- 5
- 6
- -
- 7
- 8
- 9
- $\frac{a}{b}$
- .
- 0
- =
- %
- $a^n$
- $a^{\circ}$
- $a_n$
- $\sqrt{}$
- $\sqrt[n]{}$
- $\pi$
- $\ln{}$
- $\log$
- $\theta$
- $\sin{}$
- $\cos{}$
- $\tan{}$
- $($
- $)$
- $[$
- $]$
- $\cap$
- $\cup$
- $,$
- $\infty$
Solution
Let $ h $ be the number of 4 unit line segments and $ v $ be the number of 5 unit line segments. Then $ 4h+5v=2007 $. Each pair of adjacent 4 unit line segments and each pair of adjacent 5 unit line segments determine one basic rectangle. Thus the number of basic rectangles determined is $ B = (h - 1)(v - 1) $. To simplify the work, make the substitutions $ x = h - 1 $ and $ y = v - 1 $. The problem is now to maximize $ B = xy $ subject to $ 4x + 5y = 1998 $, where $ x $, $ y $ are integers. Solve the second equation for $ y $ to obtain $$y =
\frac{1998}{5} - \frac{4}{5}x,$$and substitute into $ B=xy $ to obtain $$B = x\left(\frac{1998}{5} - \frac{4}{5}x\right).$$The graph of this equation is a parabola with $ x $ intercepts 0 and 999/2. The vertex of the parabola is halfway between the intercepts, at $ x = 999/4 $. This is the point at which $ B $ assumes its maximum.
However, this corresponds to a nonintegral value of $ x $ (and hence $ h $). From $ 4x+5y = 1998 $ both $ x $ and $ y $ are integers if and only if $ x \equiv 2 \pmod{5} $. The nearest such integer to $ 999/4 =
249.75 $ is $ x = 252 $. Then $ y = 198 $, and this gives the maximal value for $ B $ for which both $ x $ and $ y $ are integers. This maximal value for $ B $ is $ 252 \cdot 198 = \boxed{49896} $.
Freeflows