Question

Un arreglo triangular de números tiene una primera fila formada por los enteros impares $1, 3, 5, \ldots, 99$ en orden creciente. Cada fila debajo de la primera tiene una entrada menos que la fila que está encima, y la fila inferior tiene una sola entrada. Cada entrada de cualquier fila después de la fila superior es igual a la suma de las dos entradas diagonalmente encima de ella en la fila inmediatamente superior. ¿Cuántas entradas del arreglo son múltiplos de $67$ ? $\scriptsize\begin{array}{ccccccccccc} 1 & & 3 & & 5 & & \cdots & & 97 & & 99 \\ & 4 & & 8 & & 12 & & \cdots & & 196 & \\ & & & & & \vdots & & & & & \end{array}$

A triangular array of numbers has a first row consisting of the odd integers $1, 3, 5, \ldots, 99$ in increasing order. Each row below the first has one fewer entry than the row above it, and the bottom row has a single entry. Each entry in any row after the top row equals the sum of the two entries diagonally above it in the row immediately above it. How many entries in the array are multiples of $67?$ $\scriptsize\begin{array}{ccccccccccc} 1 & & 3 & & 5 & & \cdots & & 97 & & 99 \\ & 4 & & 8 & & 12 & & \cdots & & 196 & \\ & & & & & \vdots & & & & & \end{array}$

Respuesta

Solución:

Por inducción, la $n$ -ésima entrada de la fila $r$ es $2^{r-1}(r + 2n - 2):$ la fila $1$ da $2^0(2n - 1),$ y sumar dos entradas adyacentes de la fila $r$ da $2^{r-1}(r + 2n - 2)$ $+ 2^{r-1}(r + 2n)$ $= 2^r\bigl((r + 1) + 2n - 2\bigr),$ la fórmula para la fila $r + 1.$ La fila $r$ tiene $51 - r$ entradas, así que $1 \le n \le 51 - r.$

Como $67$ es impar, una entrada es múltiplo de $67$ exactamente cuando $67 \mid r + 2n - 2.$ A medida que $n$ recorre la fila $r,$ la cantidad $r + 2n - 2$ toma los valores $r, r + 2, \ldots, 100 - r,$ todos con la misma paridad que $r$ y todos menores que $134.$ Así que el único múltiplo posible de $67$ es el propio $67$ , lo que requiere que $r$ sea impar y $r \le 67 \le 100 - r,$ es decir, $r \le 33.$

Cada fila impar $r = 1, 3, \ldots, 33$ contiene exactamente una entrada de este tipo, para un total de $17.$

By induction, the $n$ th entry of row $r$ is $2^{r-1}(r + 2n - 2):$ row $1$ gives $2^0(2n - 1),$ and summing two adjacent entries of row $r$ gives $2^{r-1}(r + 2n - 2)$ $+ 2^{r-1}(r + 2n)$ $= 2^r\bigl((r + 1) + 2n - 2\bigr),$ the formula for row $r + 1.$ Row $r$ has $51 - r$ entries, so $1 \le n \le 51 - r.$

Since $67$ is odd, an entry is a multiple of $67$ exactly when $67 \mid r + 2n - 2.$ As $n$ runs through row $r,$ the quantity $r + 2n - 2$ takes the values $r, r + 2, \ldots, 100 - r,$ all with the same parity as $r$ and all less than $134.$ So the only possible multiple of $67$ is $67$ itself, which requires $r$ odd and $r \le 67 \le 100 - r,$ that is, $r \le 33.$

Each odd row $r = 1, 3, \ldots, 33$ contains exactly one such entry, for a total of $17.$

2008 AIME I Problema 6

Solución:

El Problema 6 en otros años