1993 AMC 12 Problem 30

Question

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

infinitely many

Each step takes the fractional part of twice the preceding value

Thus

x_5

is the fractional part of

32x_0

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.

Problem 30 in other years