AIME II Problem 8 2007

[zefuri]

A rectangular piece of 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.

[AuSmith]

This is surprisingly similar to that fence problem we worked from the calculator contest, where you had to devote as much fence going north as you did south.

If you draw a lines of length 4 and b lines of length 5 provided that [unparseable or potentially dangerous latex formula], you have [unparseable or potentially dangerous latex formula] "basic rectangles." (edit: Oh yea! ... sides of the paper don't count as edges.)


Notice that at any time (that we care about), we may add or subtract 5 from a in order to subtract or add 4 to b. Also, whenever [unparseable or potentially dangerous latex formula], assuming it's between 0 and 500, there is an integer b that satisfies the "exactly 2007 units" requirement.

[unparseable or potentially dangerous latex formula], which just a parabola. Maxes out at [unparseable or potentially dangerous latex formula], or [unparseable or potentially dangerous latex formula]. But remember, a must be 3 more than a multiple of 5. Since parabolas are symmetric about their axis, we can automatically take [unparseable or potentially dangerous latex formula], since it's closer to the vertex than [unparseable or potentially dangerous latex formula]. Now, since [unparseable or potentially dangerous latex formula], [unparseable or potentially dangerous latex formula]

[unparseable or potentially dangerous latex formula], but you only had to do the last three digits, of course.