Question

En un arreglo rectangular de puntos, con $5$ filas y $N$ columnas, los puntos se numeran consecutivamente de izquierda a derecha comenzando por la fila superior. Así, la fila superior se numera de $1$ a $N,$ la segunda fila se numera de $N + 1$ a $2N,$ y así sucesivamente. Se seleccionan cinco puntos, $P_1,$ $P_2,$ $P_3,$ $P_4,$ y $P_5,$ de modo que cada $P_i$ está en la fila $i.$ Sea $x_i$ el número asociado a $P_i.$ Ahora se renumera el arreglo consecutivamente de arriba abajo, comenzando por la primera columna. Sea $y_i$ el número asociado a $P_i$ después de renumerar.

Se encuentra que $x_1 = y_2,$ $x_2 = y_1,$ $x_3 = y_4,$ $x_4 = y_5,$ y $x_5 = y_3.$ Halla el menor valor posible de $N.$

In a rectangular array of points, with $5$ rows and $N$ columns, the points are numbered consecutively from left to right beginning with the top row. Thus the top row is numbered $1$ through $N,$ the second row is numbered $N + 1$ through $2N,$ and so forth. Five points, $P_1,$ $P_2,$ $P_3,$ $P_4,$ and $P_5,$ are selected so that each $P_i$ is in row $i.$ Let $x_i$ be the number associated with $P_i.$ Now renumber the array consecutively from top to bottom, beginning with the first column. Let $y_i$ be the number associated with $P_i$ after renumbering.

It is found that $x_1 = y_2,$ $x_2 = y_1,$ $x_3 = y_4,$ $x_4 = y_5,$ and $x_5 = y_3.$ Find the smallest possible value of $N.$

Respuesta

Solución:

Sea $P_i$ en la columna $c_i.$ Entonces $x_i = (i-1)N + c_i$ y $y_i = 5(c_i - 1) + i.$ Las cinco condiciones se convierten en $\begin{aligned} c_1 &= 5c_2 - 3, \\ N + c_2 &= 5c_1 - 4, \\ 2N + c_3 &= 5c_4 - 1, \end{aligned}$ $\begin{aligned} 3N + c_4 &= 5c_5, \\ 4N + c_5 &= 5c_3 - 2. \end{aligned}$

Sustituyendo $c_1 = 5c_2 - 3$ en la segunda ecuación se obtiene $N = 24c_2 - 19.$ Eliminando $c_3$ y $c_4$ de las tres últimas ecuaciones se obtiene $124 c_5 = 89N + 7.$ Sustituyendo $N = 24c_2 - 19$ y reduciendo, $31 \mid 534 c_2 - 421,$ es decir $7 c_2 \equiv 18 \pmod{31},$ cuya menor solución positiva es $c_2 = 7.$

Entonces $N = 24 \cdot 7 - 19 = 149,$ y sustituyendo hacia atrás se obtienen columnas válidas $(c_1, \ldots, c_5) = (32, 7, 107, 45, 86),$ todas a lo sumo $149.$ Así el menor valor posible de $N$ es $149.$

Let $P_i$ sit in column $c_i.$ Then $x_i = (i-1)N + c_i$ and $y_i = 5(c_i - 1) + i.$ The five conditions become $\begin{aligned} c_1 &= 5c_2 - 3, \\ N + c_2 &= 5c_1 - 4, \\ 2N + c_3 &= 5c_4 - 1, \end{aligned}$ $\begin{aligned} 3N + c_4 &= 5c_5, \\ 4N + c_5 &= 5c_3 - 2. \end{aligned}$

Substituting $c_1 = 5c_2 - 3$ into the second equation gives $N = 24c_2 - 19.$ Eliminating $c_3$ and $c_4$ from the last three equations yields $124 c_5 = 89N + 7.$ Substituting $N = 24c_2 - 19$ and reducing, $31 \mid 534 c_2 - 421,$ i.e. $7 c_2 \equiv 18 \pmod{31},$ whose smallest positive solution is $c_2 = 7.$

Then $N = 24 \cdot 7 - 19 = 149,$ and back-substituting gives valid columns $(c_1, \ldots, c_5) = (32, 7, 107, 45, 86),$ all at most $149.$ So the smallest possible $N$ is $149.$

2001 AIME I Problema 11

Solución:

El Problema 11 en otros años