Question

Un arreglo triangular de cuadrados tiene un cuadrado en la primera fila, dos en la segunda y, en general, $k$ cuadrados en la $k$ -ésima fila para $1 \le k \le 11.$ Con la excepción de la fila inferior, cada cuadrado descansa sobre dos cuadrados de la fila inmediatamente inferior, como se ilustra en la figura. En cada cuadrado de la undécima fila se coloca un $0$ o un $1$ . Luego se colocan números en los demás cuadrados, siendo la entrada de cada cuadrado la suma de las entradas de los dos cuadrados debajo de él. ¿Para cuántas distribuciones iniciales de $0$ y $1$ en la fila inferior el número del cuadrado superior es múltiplo de $3$ ?

A triangular array of squares has one square in the first row, two in the second, and, in general, $k$ squares in the $k$ th row for $1 \le k \le 11.$ With the exception of the bottom row, each square rests on two squares in the row immediately below, as illustrated in the figure. In each square of the eleventh row, a $0$ or a $1$ is placed. Numbers are then placed into the other squares, with the entry for each square being the sum of the entries in the two squares below it. For how many initial distributions of $0$ 's and $1$ 's in the bottom row is the number in the top square a multiple of $3?$

Respuesta

Solución:

Etiqueta las entradas de la fila inferior como $x_0, x_1, \ldots, x_{10}.$ Como cada cuadrado es la suma de los dos que tiene debajo, las contribuciones se acumulan con los pesos del triángulo de Pascal: el cuadrado superior es igual a $\sum_{i=0}^{10} \binom{10}{i} x_i.$

Módulo $3,$ la comprobación directa (o el teorema de Lucas con $10 = 101_3$ ) muestra que $\binom{10}{i} \equiv 0$ para $2 \le i \le 8,$ mientras que $\binom{10}{0} = \binom{10}{10} = 1$ y $\binom{10}{1} = \binom{10}{9} = 10 \equiv 1.$ Así que el cuadrado superior es múltiplo de $3$ exactamente cuando $x_0 + x_1 + x_9 + x_{10}$ $\equiv 0 \pmod 3.$

Para entradas $0$ / $1$ esta suma es $0$ o $3:$ o bien los cuatro son $0$ (una manera) o bien exactamente tres son $1$ (cuatro maneras), dando $5$ opciones. Las siete entradas restantes $x_2, \ldots, x_8$ son libres, así que el total es $5 \cdot 2^7 = 640.$

Label the bottom-row entries $x_0, x_1, \ldots, x_{10}.$ Since each square is the sum of the two below it, the contributions accumulate with Pascal's-triangle weights: the top square equals $\sum_{i=0}^{10} \binom{10}{i} x_i.$

Modulo $3,$ direct checking (or Lucas' theorem with $10 = 101_3$ ) shows $\binom{10}{i} \equiv 0$ for $2 \le i \le 8,$ while $\binom{10}{0} = \binom{10}{10} = 1$ and $\binom{10}{1} = \binom{10}{9} = 10 \equiv 1.$ So the top square is a multiple of $3$ exactly when $x_0 + x_1 + x_9 + x_{10}$ $\equiv 0 \pmod 3.$

For $0$ / $1$ entries this sum is $0$ or $3:$ either all four are $0$ (one way) or exactly three are $1$ (four ways), for $5$ choices. The remaining seven entries $x_2, \ldots, x_8$ are free, so the count is $5 \cdot 2^7 = 640.$

2007 AIME II Problema 13

Solución:

El Problema 13 en otros años