Question

一张长方形纸片的尺寸为 $4$ 单位乘 $5$ 单位。若干条线段被画出，并且都平行于纸片的边。由其中一些线段的交点确定的长方形称为基本长方形，如果 (i) 该长方形的四条边都是所画线段的一部分，且 (ii) 没有所画线段的任何一段位于该长方形内部。

已知所有画出的线段总长度恰好为 $2007$ 个单位。令 $N$ 为能确定的基本长方形个数的最大可能值。求 $N$ 除以 $1000$ 的余数。

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.$

答案

答案：896

知识点：最优化二次方程模运算

难度评级：2840

解答：

设画出的线段中有 $h$ 条长度为 $4$ ，有 $v$ 条长度为 $5$ ，则 $4h + 5v = 2007$ 。一个基本长方形由每个方向上的两条相邻线段围成，所以这些线段确定 $(h - 1)(v - 1)$ 个基本长方形。令 $x = h - 1$ 且 $y = v - 1$ ，我们要在 $4x + 5y = 1998$ 的条件下最大化 $xy$ 。

作为 $x$ 的函数，乘积 $xy = x \cdot \frac{1998 - 4x}{5}$ 是开口向下的抛物线，顶点在 $x = \frac{999}{4} = 249.75$ 。为了使 $y$ 为整数，需要 $4x \equiv 1998 \pmod 5$ ，即 $x \equiv 2 \pmod 5$ 。最近的候选是 $x = 247$ （此时 $y = 202$ ，乘积 $49894$ ）和 $x = 252$ （此时 $y = 198$ ，乘积 $49896$ ）。

因此 $N = 49896$ ，除以 $1000$ 的余数为 $896$ 。

Suppose $h$ of the drawn lines have length $4$ and $v$ have length $5,$ so $4h + 5v = 2007.$ A basic rectangle is bounded by two adjacent lines in each direction, so the lines determine $(h - 1)(v - 1)$ basic rectangles. Setting $x = h - 1$ and $y = v - 1,$ we must maximize $xy$ subject to $4x + 5y = 1998.$

As a function of $x,$ the product $xy = x \cdot \frac{1998 - 4x}{5}$ is a downward parabola with vertex at $x = \frac{999}{4} = 249.75.$ For $y$ to be an integer we need $4x \equiv 1998 \pmod 5,$ i.e. $x \equiv 2 \pmod 5.$ The nearest candidates are $x = 247$ (giving $y = 202$ and product $49894$ ) and $x = 252$ (giving $y = 198$ and product $49896$ ).

So $N = 49896,$ and the remainder upon division by $1000$ is $896.$

2007 AIME II 第 8 题

答案：896

难度评级：2840

解答：

其他年份的第 8 题