1987 AMC 12 Problema 29

Question

Considera la sucesión definida recursivamente por

t_1=1

y, para

n\gt1,

por

t_n=1+t_{\frac{n}{2}}

cuando

n

es par y por

t_n=\frac{1}{t_{n-1}}

cuando

n

es impar. Dado que

t_n=\frac{19}{87},

la suma de los dígitos de

n

es

Consider the sequence of numbers defined recursively by

t_1=1

and for

n\gt1

by

t_n=1+t_{\frac{n}{2}}

when

n

is even and by

t_n=\frac{1}{t_{n-1}}

when

n

is odd. Given that

t_n=\frac{19}{87},

the sum of the digits of

n

is

15

17

19

21

23

Respuesta: A

Conceptos:recursive sequence inverse recursion rational numbers

Nivel de dificultad: 2440

Pista pequeña:

Los valores mayores que

1

provienen de índices pares; los valores entre

0

y

1

provienen de índices impares

Values greater than

1

come from even indices; values between

0

and

1

come from odd indices

Pista grande:

Invierte la recurrencia: resta

1

a los valores mayores que

1

y toma el recíproco de los valores menores que

1

Reverse the recursion by subtracting

1

from values above

1

and taking reciprocals of values below

1

Solución:

Sea

N(r)

el índice en el que aparece el valor

r

. Al invertir la recurrencia, se obtiene

N(r)=2N(r-1)

para

r\gt1,

y

N(r)=N(\frac{1}{r})+1

para

0\lt r\lt1.

Partiendo de

N(1)=1,

el uso repetido de estas relaciones da

N(2)=2,

N(\frac{1}{2})=3,

N(\frac{3}{2})=6,

y

N(\frac{2}{3})=7.

Al continuar, se obtiene

N(\frac{5}{3})=14,

N(\frac{8}{3})=28,

N(\frac{3}{8})=29,

y

N(\frac{11}{8})=58.

Luego,

N(\frac{8}{11})=59,

N(\frac{19}{11})=118,

N(\frac{11}{19})=119,

N(\frac{30}{19})=238,

N(\frac{49}{19})=476,

y

N(\frac{68}{19})=952.

Finalmente,

N(\frac{87}{19})=1904

y

N(\frac{19}{87})=1905.

Así,

n=1905,

cuya suma de dígitos es

1+9+0+5=15.

Por lo tanto, la respuesta correcta es A.

Let

N(r)

be the index at which the value

r

occurs. Reversing the recursion gives

N(r)=2N(r-1)

for

r\gt1,

and

N(r)=N(\frac{1}{r})+1

for

0\lt r\lt1.

Starting with

N(1)=1,

repeated use gives

N(2)=2,

N(\frac{1}{2})=3,

N(\frac{3}{2})=6,

and

N(\frac{2}{3})=7.

Continuing gives

N(\frac{5}{3})=14,

N(\frac{8}{3})=28,

N(\frac{3}{8})=29,

and

N(\frac{11}{8})=58.

Next,

N(\frac{8}{11})=59,

N(\frac{19}{11})=118,

N(\frac{11}{19})=119,

N(\frac{30}{19})=238,

N(\frac{49}{19})=476,

and

N(\frac{68}{19})=952.

Finally,

N(\frac{87}{19})=1904

and

N(\frac{19}{87})=1905.

Thus

n=1905,

whose digit sum is

1+9+0+5=15.

Therefore the correct answer is A.