Question

Una hoja rectangular de papel mide $4$ unidades por $5$ unidades. Se dibujan varias líneas paralelas a los bordes del papel. Un rectángulo determinado por las intersecciones de algunas de estas líneas se llama básico si (i) los cuatro lados del rectángulo son segmentos de líneas dibujadas, y (ii) ningún segmento de línea dibujada queda dentro del rectángulo.

Dado que la longitud total de todas las líneas dibujadas es exactamente $2007$ unidades, sea $N$ el máximo número posible de rectángulos básicos determinados. ¿Cuál es el residuo cuando $N$ se divide entre $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.$

Respuesta

Solución:

Supón que $h$ de las líneas dibujadas tienen longitud $4$ y $v$ tienen longitud $5,$ de modo que $4h + 5v = 2007.$ Un rectángulo básico está limitado por dos líneas adyacentes en cada dirección, así que las líneas determinan $(h - 1)(v - 1)$ rectángulos básicos. Poniendo $x = h - 1$ y $y = v - 1,$ debemos maximizar $xy$ sujeto a $4x + 5y = 1998.$

Como función de $x,$ el producto $xy = x \cdot \frac{1998 - 4x}{5}$ es una parábola hacia abajo con vértice en $x = \frac{999}{4} = 249.75.$ Para que $y$ sea entero necesitamos $4x \equiv 1998 \pmod 5,$ es decir $x \equiv 2 \pmod 5.$ Los candidatos más cercanos son $x = 247$ (que da $y = 202$ y producto $49894$ ) y $x = 252$ (que da $y = 198$ y producto $49896$ ).

Así que $N = 49896,$ y el residuo al dividir entre $1000$ es $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 Problema 8

Solución:

El Problema 8 en otros años