Question

Para enteros $a$ y $b,$ definimos $a \circ b = a - b$ si $a$ es impar y $b$ es par, y $a \circ b = a + b$ en caso contrario. Halla el número de sucesiones $a_1, a_2, a_3, \ldots, a_n$ de enteros positivos tales que $a_1 + a_2 + a_3 + \cdots + a_n = 12$ y $a_1 \circ a_2 \circ a_3 \circ \cdots \circ a_n = 0,$ donde las operaciones se realizan de izquierda a derecha; es decir, $a_1 \circ a_2 \circ a_3$ significa $(a_1 \circ a_2) \circ a_3.$

For integers $a$ and $b,$ let $a \circ b = a - b$ if $a$ is odd and $b$ is even, and $a \circ b = a + b$ otherwise. Find the number of sequences $a_1, a_2, a_3, \ldots, a_n$ of positive integers such that $a_1 + a_2 + a_3 + \cdots + a_n = 12$ and $a_1 \circ a_2 \circ a_3 \circ \cdots \circ a_n = 0,$ where the operations are performed from left to right; that is, $a_1 \circ a_2 \circ a_3$ means $(a_1 \circ a_2) \circ a_3.$

Respuesta

Solución:

Como $a - b \equiv a + b \pmod 2,$ el valor acumulado tras $k$ pasos tiene la misma paridad que $a_1 + \cdots + a_k.$ Así que el término $a_k$ se resta exactamente cuando $a_k$ es par y la suma prefija $a_1 + \cdots + a_{k-1}$ es impar, y el valor final es $12$ menos el doble del total de los términos restados. Debemos contar las composiciones de $12$ en las que los términos pares situados donde la suma prefija es impar suman exactamente $6.$ La paridad prefija cambia exactamente en los términos impares, así que los términos impares vienen en número $2m$ (el total es par), y los términos restados son precisamente los términos pares que están entre el $(2i-1)$ -ésimo y el $2i$ -ésimo términos impares; estos $m$ "tramos impares" deben contener términos pares que sumen $6,$ mientras que los otros $m + 1$ tramos contienen términos pares que suman $6 - A,$ donde $A$ es la suma de los términos impares.

Sea $f_r(t)$ el número de maneras de llenar $r$ tramos ordenados con sucesiones de términos pares que suman $2t.$ Un tramo es una composición de $2t$ en partes pares, es decir, de $t:$ $f_1(t) = 2^{t-1}$ para $t \ge 1$ y $f_1(0) = 1;$ al convolucionar se obtienen los valores necesarios más abajo: $f_r(0) = 1,$ $f_r(1) = r,$ $f_2(2) = 5,$ y $f_1(3), f_2(3), f_3(3) = 4, 12, 25.$ Las composiciones de $A$ en $2m$ partes impares son en número $\binom{(A - 2m)/2 + 2m - 1}{2m - 1}.$

Análisis por casos según $m$ y $A:$ para $m = 1:$ $A = 2, 4, 6$ dan $1 \cdot 4 \cdot f_2(2) = 20,$ $2 \cdot 4 \cdot f_2(1) = 16,$ y $3 \cdot 4 \cdot 1 = 12.$ Para $m = 2:$ $A = 4, 6$ dan $1 \cdot 12 \cdot f_3(1) = 36$ y $4 \cdot 12 \cdot 1 = 48.$ Para $m = 3:$ $A = 6$ da $1 \cdot 25 \cdot 1 = 25.$ El total es $20 + 16 + 12 + 36$ $+ 48 + 25 = 157.$

Since $a - b \equiv a + b \pmod 2,$ the running value after $k$ steps has the same parity as $a_1 + \cdots + a_k.$ So term $a_k$ is subtracted exactly when $a_k$ is even and the prefix sum $a_1 + \cdots + a_{k-1}$ is odd, and the final value is $12$ minus twice the total of the subtracted terms. We must count compositions of $12$ in which the even terms sitting where the prefix sum is odd total exactly $6.$ The prefix parity flips exactly at odd terms, so the odd terms come in $2m$ (the total is even), and the subtracted terms are precisely the even terms lying between the $(2i-1)$ st and $2i$ th odd terms; these $m$ "odd stretches" must hold even terms totaling $6,$ while the other $m + 1$ stretches hold even terms totaling $6 - A,$ where $A$ is the sum of the odd terms.

Let $f_r(t)$ be the number of ways to fill $r$ ordered stretches with sequences of even terms totaling $2t.$ One stretch is a composition of $2t$ into even parts, i.e. of $t:$ $f_1(t) = 2^{t-1}$ for $t \ge 1$ and $f_1(0) = 1;$ convolving gives the values needed below: $f_r(0) = 1,$ $f_r(1) = r,$ $f_2(2) = 5,$ and $f_1(3), f_2(3), f_3(3) = 4, 12, 25.$ Compositions of $A$ into $2m$ odd parts number $\binom{(A - 2m)/2 + 2m - 1}{2m - 1}.$

Casework on $m$ and $A:$ for $m = 1:$ $A = 2, 4, 6$ give $1 \cdot 4 \cdot f_2(2) = 20,$ $2 \cdot 4 \cdot f_2(1) = 16,$ and $3 \cdot 4 \cdot 1 = 12.$ For $m = 2:$ $A = 4, 6$ give $1 \cdot 12 \cdot f_3(1) = 36$ and $4 \cdot 12 \cdot 1 = 48.$ For $m = 3:$ $A = 6$ gives $1 \cdot 25 \cdot 1 = 25.$ The total is $20 + 16 + 12 + 36$ $+ 48 + 25 = 157.$

2026 AIME II Problema 14

Solución:

El Problema 14 en otros años