1993 AMC 12 Problema 30

Question

Dado

0\le x_0\lt1,

define

x_n= \begin{cases} 2x_{n-1},&\text{si }2x_{n-1}\lt1,\\ 2x_{n-1}-1,&\text{si }2x_{n-1}\ge1 \end{cases}

para todo entero

n\gt0.

¿Para cuántos valores de

x_0

se cumple

x_0=x_5

?

Given

0\le x_0\lt1,

let

x_n= \begin{cases} 2x_{n-1},&\text{if }2x_{n-1}\lt1,\\ 2x_{n-1}-1,&\text{if }2x_{n-1}\ge1 \end{cases}

for all integers

n\gt0.

For how many

x_0

is it true that

x_0=x_5?

0

1

5

31

infinitos

infinitely many

Respuesta: D

Conceptos:iteration fractional part modular equation

Nivel de dificultad: 2380

Pista pequeña:

Cada paso toma la parte fraccionaria del doble del valor anterior

Each step takes the fractional part of twice the preceding value

Pista grande:

Por lo tanto,

x_5

es la parte fraccionaria de

32x_0

Thus

x_5

is the fractional part of

32x_0

Solución:

La recurrencia es

x_n=\{2x_{n-1}\},

por lo que

x_5=\{32x_0\}.

La igualdad

x_5=x_0

exige

32x_0-x_0=\lfloor32x_0\rfloor,

y, por tanto,

31x_0

es un entero. Los valores

x_0=\frac{k}{31}

para

k=0,

1,

\ldots,

30

satisfacen la recurrencia y pertenecen a

[0,1).

Hay

31

valores. Por lo tanto, la respuesta correcta es D.

The recurrence is

x_n=\{2x_{n-1}\},

so

x_5=\{32x_0\}.

The equality

x_5=x_0

requires

32x_0-x_0=\lfloor32x_0\rfloor,

hence

31x_0

is an integer. The values

x_0=\frac{k}{31}

for

k=0,

1,

\ldots,

30

all satisfy the recurrence and lie in

[0,1).

There are

31

values. Thus the correct answer is D.