Question

Para $n \ge 1$ diga que una sucesión finita $(a_1, a_2, \ldots, a_n)$ de enteros positivos es progresiva si $a_i \lt a_{i+1}$ y $a_i$ divide a $a_{i+1}$ para $1 \le i \le n - 1.$ Halle el número de sucesiones progresivas tales que la suma de los términos de la sucesión sea igual a $360.$

For $n \ge 1$ call a finite sequence $(a_1, a_2, \ldots, a_n)$ of positive integers progressive if $a_i \lt a_{i+1}$ and $a_i$ divides $a_{i+1}$ for $1 \le i \le n - 1.$ Find the number of progressive sequences such that the sum of the terms in the sequence is equal to $360.$

Respuesta

Solución:

La divisibilidad es transitiva, así que cada término de una sucesión progresiva es múltiplo del primer término. Si una sucesión con suma $360$ tiene longitud al menos $2$ y primer término $d,$ entonces $d \mid 360,$ y dividir los términos restantes entre $d$ produce una sucesión progresiva con primer término al menos $2$ y suma $\frac{360 - d}{d} = \frac{360}{d} - 1;$ esta correspondencia es reversible. Por lo tanto, si $g(s)$ denota el número de sucesiones progresivas con suma $s$ y primer término al menos $2,$ la respuesta es $1 + \sum_{d \mid 360,\, d \lt 360} g\!\left(\frac{360}{d} - 1\right),$ donde el $1$ inicial cuenta la sucesión $(360).$

La misma reducción da la recursión $\begin{aligned} g(s) &= 1 + \sum_{\substack{e \mid s \\ 2 \le e \lt s}} g\!\left(\frac{s}{e} - 1\right) \\ &\qquad (s \ge 2), \end{aligned}$ con $g(1) = 0;$ en particular $g(s) = 1$ cuando $s$ es primo. Avanzando hacia arriba: $g(2) = g(3) = g(4)$ $= g(5) = g(7) = 1;$ $g(6) = 1 + g(2) = 2;$ $g(8) = 1 + g(3) = 2;$ $g(9) = 1 + g(2) = 2;$ $g(10) = 1 + g(4) = 2;$ $g(12) = 1 + g(5) + g(3) + g(2)$ $= 4;$ $g(14) = 1 + g(6) = 3;$ $g(16) = 1 + g(7) + g(3) = 3;$ $g(21) = 1 + g(6) + g(2) = 4;$ $g(35) = 1 + g(6) + g(4) = 4;$ $g(39) = 1 + g(12) + g(2) = 6;$ $g(44) = 1 + g(21) + g(10)$ $+ g(3) = 8;$ $g(119) = 1 + g(16) + g(6) = 6.$

Los $23$ divisores $d \lt 360$ dan los argumentos $\frac{360}{d} - 1 = 359,$ $179,$ $119,$ $89,$ $71,$ $59,$ $44,$ $39,$ $35,$ $29,$ $23,$ $19,$ $17,$ $14,$ $11,$ $9,$ $8,$ $7,$ $5,$ $4,$ $3,$ $2,$ $1,$ cuyos valores de $g$ son $1, 1, 6, 1,$ $1, 1, 8, 6,$ $4, 1, 1, 1,$ $1, 3, 1, 2,$ $2, 1, 1, 1,$ $1, 1, 0,$ que suman $46.$ Sumando la sucesión de un solo término se obtiene $46 + 1 = 47.$

Divisibility is transitive, so every term of a progressive sequence is a multiple of the first term. If a sequence with sum $360$ has length at least $2$ and first term $d,$ then $d \mid 360,$ and dividing the remaining terms by $d$ yields a progressive sequence with first term at least $2$ and sum $\frac{360 - d}{d} = \frac{360}{d} - 1;$ this correspondence is reversible. So if $g(s)$ denotes the number of progressive sequences with sum $s$ and first term at least $2,$ the answer is $1 + \sum_{d \mid 360,\, d \lt 360} g\!\left(\frac{360}{d} - 1\right),$ the leading $1$ counting the sequence $(360).$

The same reduction gives the recursion $\begin{aligned} g(s) &= 1 + \sum_{\substack{e \mid s \\ 2 \le e \lt s}} g\!\left(\frac{s}{e} - 1\right) \\ &\qquad (s \ge 2), \end{aligned}$ with $g(1) = 0;$ in particular $g(s) = 1$ when $s$ is prime. Working upward: $g(2) = g(3) = g(4)$ $= g(5) = g(7) = 1;$ $g(6) = 1 + g(2) = 2;$ $g(8) = 1 + g(3) = 2;$ $g(9) = 1 + g(2) = 2;$ $g(10) = 1 + g(4) = 2;$ $g(12) = 1 + g(5) + g(3) + g(2)$ $= 4;$ $g(14) = 1 + g(6) = 3;$ $g(16) = 1 + g(7) + g(3) = 3;$ $g(21) = 1 + g(6) + g(2) = 4;$ $g(35) = 1 + g(6) + g(4) = 4;$ $g(39) = 1 + g(12) + g(2) = 6;$ $g(44) = 1 + g(21) + g(10)$ $+ g(3) = 8;$ $g(119) = 1 + g(16) + g(6) = 6.$

The $23$ divisors $d \lt 360$ give arguments $\frac{360}{d} - 1 = 359,$ $179,$ $119,$ $89,$ $71,$ $59,$ $44,$ $39,$ $35,$ $29,$ $23,$ $19,$ $17,$ $14,$ $11,$ $9,$ $8,$ $7,$ $5,$ $4,$ $3,$ $2,$ $1,$ whose $g$ -values are $1, 1, 6, 1,$ $1, 1, 8, 6,$ $4, 1, 1, 1,$ $1, 3, 1, 2,$ $2, 1, 1, 1,$ $1, 1, 0,$ summing to $46.$ Adding the single-term sequence gives $46 + 1 = 47.$

2019 AIME II Problema 12

Solución:

El Problema 12 en otros años