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

Respuesta: 47

Conceptos:conteo recursivo divisibilidad

Nivel de dificultad: 3060

Pista pequeña:

Cada término es múltiplo del primer término, así que

a_1

divide a

360;

divídalo para obtener una sucesión progresiva más corta con primer término al menos

2

Every term is a multiple of the first term, so

a_1

divides

360;

divide it out to get a shorter progressive sequence with first term at least

2

Pista grande:

Sea

g(s)

el número de sucesiones progresivas con suma

s

y primer término al menos

2;

entonces

g(s) = 1 + \sum g(\frac{s}{e} - 1)

sobre los divisores

e

de

s

con

2 \le e \lt s

Let

g(s)

count progressive sequences with sum

s

and first term at least

2;

then

g(s) = 1 + \sum g(\frac{s}{e} - 1)

over divisors

e

of

s

with

2 \le e \lt s

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

divide a

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. Calculando en orden creciente:

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

divides

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

Respuesta: 47

Nivel de dificultad: 3060

Pista pequeña:

Pista grande:

Solución:

El Problema 12 en otros años