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

Answer: D

Concepts:iteration fractional part modular equation

Difficulty rating: 2380

Small Hint:

Each step takes the fractional part of twice the preceding value

Big Hint:

Thus $x_5$ is the fractional part of $32x_0$

Solution:

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.

1993 AMC 12 Problem 30

Answer: D

Difficulty rating: 2380

Small Hint:

Big Hint:

Solution:

Problem 30 in Other Years