2007 AIME II Problems/Problem 8

Revision as of 20:40, 29 March 2007 by Azjps (talk | contribs) (add solution)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

A rectangular piece of paper measures 4 units by 5 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 2007 units, let $N$ be the maximum possible number of basic rectangles determined. Find the remainder when $N$ is divided by 1000.

Solution

Denote the number of horizontal lines as $x$, and the number of vertical lines as $y$. The number of basic rectangles is $(x - 1)(y - 1)$. $5x + 4y = 2007 \Longrightarrow y = \frac{2007 - 5x}{4}$. Substituting, we find that $(x - 1)\left(-\frac 54x + \frac{2003}4\right)$.

FOIL this to get a quadratic, $-\frac 54x^2 + 502x - \frac{2003}4$. Use $\frac{-b}{2a}$ to find the maximum possible value of the quadratic: $x = \frac{-502}{-2 \cdot \frac 54} = \frac{1004}5 \approx 201$. However, this gives a non-integral answer for $y$. The closest two values that work are $(199,253)$ and $(203,248)$.

We see that $252 \cdot 198 = 49896 > 202 \cdot 247 = 49894$. The solution is $896$.

See also

2007 AIME II (ProblemsAnswer KeyResources)
Preceded by
Problem 1
Followed by
Problem 3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions