Question

El diagrama de abajo muestra un arreglo rectangular de puntos de $4 \times 4,$ cada uno de los cuales está a $1$ unidad de distancia de sus vecinos más cercanos.

Define un camino creciente como una sucesión de puntos distintos del arreglo con la propiedad de que la distancia entre puntos consecutivos de la sucesión es estrictamente creciente. Sea $m$ el máximo número posible de puntos en un camino creciente, y sea $r$ el número de caminos crecientes que constan de exactamente $m$ puntos. Halla $mr.$

The diagram below shows a $4 \times 4$ rectangular array of points, each of which is $1$ unit away from its nearest neighbors.

Define a growing path to be a sequence of distinct points of the array with the property that the distance between consecutive points of the sequence is strictly increasing. Let $m$ be the maximum possible number of points in a growing path, and let $r$ be the number of growing paths consisting of exactly $m$ points. Find $mr.$

Respuesta

Solución:

La distancia al cuadrado entre dos puntos del arreglo es $a^2 + b^2,$ donde $a$ y $b$ son las diferencias de coordenadas, cada una en $\{0, 1, 2, 3\}$ y no ambas cero. Los valores posibles son $1, 2, 4, 5, 8, 9, 10, 13, 18$ , solo $9$ valores, así que un camino creciente tiene a lo sumo $10$ puntos, y un camino con $10$ puntos debe usar las nueve distancias en orden creciente. Etiqueta sus puntos $P_1, \ldots, P_{10}$ de modo que $P_1 P_2 = 1$ y $P_9 P_{10} = \sqrt{18}.$

Como $\sqrt{18}$ solo se realiza con esquinas opuestas, hay $4$ elecciones ordenadas de $(P_{10}, P_9).$ Luego, $P_8 P_9 = \sqrt{13}$ deja $2$ elecciones para $P_8,$ los dos vecinos de $P_{10},$ simétricos respecto de la diagonal principal. A partir de ahí las distancias $\sqrt{10}, 3, \sqrt{8}, \sqrt{5}, 2, \sqrt{2}$ fuerzan $P_7, P_6, \ldots, P_2$ de manera única (para $P_7$ la elección de la otra esquina falla porque el punto que se necesitaría después para $P_6$ coincidiría con $P_9$ o $P_{10}$ ). Finalmente $P_1$ debe estar a distancia $1$ de $P_2,$ y $3$ de sus vecinos quedan sin usar. Uno de los caminos resultantes se muestra abajo.

Por lo tanto $m = 10$ y $r = 4 \cdot 2 \cdot 3 = 24,$ así que $mr = 240.$

The squared distance between two points of the array is $a^2 + b^2,$ where $a$ and $b$ are the coordinate differences, each in $\{0, 1, 2, 3\}$ and not both zero. The possible values are $1, 2, 4, 5, 8, 9, 10, 13, 18$ — only $9$ values — so a growing path has at most $10$ points, and a path with $10$ points must use all nine distances in increasing order. Label its points $P_1, \ldots, P_{10}$ so that $P_1 P_2 = 1$ and $P_9 P_{10} = \sqrt{18}.$

Since $\sqrt{18}$ is realized only by opposite corners, there are $4$ ordered choices of $(P_{10}, P_9).$ Next, $P_8 P_9 = \sqrt{13}$ leaves $2$ choices for $P_8,$ the two neighbors of $P_{10},$ symmetric across the main diagonal. From there the distances $\sqrt{10}, 3, \sqrt{8}, \sqrt{5}, 2, \sqrt{2}$ force $P_7, P_6, \ldots, P_2$ uniquely (for $P_7$ the alternative corner choice fails because the point needed next for $P_6$ would coincide with $P_9$ or $P_{10}$ ). Finally $P_1$ must be at distance $1$ from $P_2,$ and $3$ of its neighbors are unused. One of the resulting paths is shown below.

Hence $m = 10$ and $r = 4 \cdot 2 \cdot 3 = 24,$ so $mr = 240.$

2008 AIME II Problema 10

Solución:

El Problema 10 en otros años