取余递推

6. 已知实数 $x_0\in[0,1)$，数列 $\{x_n\}$满足对任意的 $n\in\mathbf{N}^*$，有

$$x_n=\begin{cases}2x_{n-1}, & x_{n-1}<\dfrac{1}{2},\\[2mm] 2x_{n-1}-1, & x_{n-1}\geqslant\dfrac{1}{2}.\end{cases}$$

若 $x_{2021}=x_0$，则所有可能的 $x_0$的个数为__________。

A、$2021$　　B、$2^{2021}-1$　　C、$2^{2021}$　　D、以上答案都不对

解： 记 $\{x\}=x-[x]$为 $x$的小数部分.

我们先对问题进行粗略审视： $$x\in\left[0,\tfrac12\right)\Rightarrow 2x\in[0,1),\qquad x\in\left[\tfrac12,1\right)\Rightarrow 2x-1\in[0,1).$$由 $x_0\in[0,1)$归纳易知，$x_n\in[0,1)$（$n=1,2,\cdots$）.

于是 $2x_{n-1}\in[0,2)$：当 $2x_{n-1}<1$时，$x_n=2x_{n-1}$；当 $2x_{n-1}\geqslant1$时，$x_n=2x_{n-1}-1$. 两种情形都是取 $2x_{n-1}$的小数部分，所以题目中的递推公式其实恰是 $$x_n=\{2x_{n-1}\}.$$

我们又熟知取余函数的性质：若 $a\in\mathbf Z$，则 $$\{a\{b\}\}=\{ab\},$$这是因为 $ab-a\{b\}=a[b]\in\mathbf Z$，而相差整数的两个数小数部分相同.

那么，由归纳法即得通项公式： $$x_n=\{2x_{n-1}\}=\left\{2\{2^{n-1}x_0\}\right\}=\{2^nx_0\}.$$

要求 $x_{2021}=x_0$，即 $\{2^{2021}x_0\}=x_0$. 由于 $x_0\in[0,1)$，这等价于 $2^{2021}x_0-x_0$是整数，即 $$2^{2021}x_0=x_0+C,\qquad C=(2^{2021}-1)x_0\in\mathbf Z.$$又 $x_0\in[0,1)$，故 $C\in[0,2^{2021}-1)$，即 $C\in\{0,1,\cdots,2^{2021}-2\}$.

反之，对于每一个这样的整数 $C$，令 $x_0=\dfrac{C}{2^{2021}-1}$，则 $x_0\in[0,1)$，且 $2^{2021}x_0-x_0=C\in\mathbf Z$，满足条件；不同的 $C$对应不同的 $x_0$.

而这样的 $C$一共有 $2^{2021}-1$个，故有 $2^{2021}-1$个 $x_0$.

正确答案：B.

例 8 已知数列 $\{a_n\}$满足：$a_1\in\mathbf{N}^*$，$a_1\leqslant 36$，且

$$a_{n+1}=\begin{cases}2a_n, & a_n\leqslant 18,\\ 2a_n-36, & a_n>18\end{cases}\quad(n=1,2,\cdots).$$

记集合 $M=\{a_n \mid n\in\mathbf{N}^*\}$.

(1) 若 $a_1=6$，写出集合 $M$的所有元素；

(2) 若集合 $M$存在一个元素是 3 的倍数，证明：$M$的所有元素都是 3 的倍数；

(3) 求集合 $M$的元素个数的最大值. 解：(1) 6，12，24.

(2) 因为集合 $M$存在一个元素是 3 的倍数，所以不妨设 $a_k$是 3 的倍数.

由 $$a_{n+1}=\begin{cases}2a_n, & a_n\leqslant 18,\\ 2a_n-36, & a_n>18\end{cases}$$可归纳证明对任意 $n\geqslant k$，$a_n$是 3 的倍数.

如果 $k=1$，则 $M$的所有元素都是 3 的倍数.

如果 $k>1$，因为 $a_k=2a_{k-1}$或 $a_k=2a_{k-1}-36$，所以 $2a_{k-1}$是 3 的倍数，于是 $a_{k-1}$是 3 的倍数.

类似可得，$a_{k-2},\cdots,a_1$都是 3 的倍数.

从而对任意 $n\geqslant 1$，$a_n$是 3 的倍数，因此 $M$的所有元素都是 3 的倍数.

综上，若集合 $M$存在一个元素是 3 的倍数，则 $M$的所有元素都是 3 的倍数. (3) 先归纳证明 $a_n\in\{1,2,\cdots,36\}$：若 $a_n\leqslant 18$，则 $a_{n+1}=2a_n\in[2,36]$；若 $a_n>18$，则 $a_{n+1}=2a_n-36\in[2,36]$.

又无论哪种情形，$a_{n+1}-2a_n$都是 $36$的倍数，即 $$a_{n+1}\equiv 2a_n\pmod{36},\qquad a_n\equiv 2^{n-1}a_1\pmod{36}.$$而 $1,2,\cdots,36$模 $36$两两不同余，所以只要 $a_m\equiv a_n\pmod{36}$，就有 $a_m=a_n$.

由于 $36=4\times 9$，$2^6=64\equiv1\pmod 9$，当 $n\geqslant3$时 $4\mid 2^{n-1}$，故 $$a_{n+6}-a_n\equiv 2^{n-1}(2^6-1)a_1=2^{n-1}\cdot 63a_1\equiv0\pmod{36},$$即当 $n\geqslant 3$时 $a_{n+6}=a_n$，所以 $M=\{a_1,a_2,\cdots,a_8\}$，$|M|\leqslant 8$.

取 $a_1=1$，得 $1,2,4,8,16,32,28,20,4,\cdots$，前 $8$项互不相同，$|M|=8$.

故集合 $M$的元素个数的最大值为 $8$.

方法总结

1. 识别结构. 两道题的递推都是分段的，但每一段的斜率相同（都乘 $2$），只是为了留在某个范围内减去一个常数. 这类递推本质上是“乘 $2$再取余”：

• 实数情形（第 6 题）：$x_{n+1}=\{2x_n\}$，于是 $x_n=\{2^nx_0\}$；
• 整数情形（例 8）：$a_{n+1}\equiv 2a_n\pmod{36}$，于是 $a_n\equiv 2^{n-1}a_1\pmod{36}$.

分段递推一旦写成取余的形式，就有了通项，周期问题也就变成了数论问题.

2. 用分母（模数）求周期. 若 $x_0$是分母为 $2^s\cdot m$（$m$为奇数）的分数，则 $x_n=\{2^nx_0\}$先经过至多 $s$项的“预周期”，之后以 $2$模 $m$的阶为周期循环. 例 8 中 $36=2^2\times 9$，预周期为 $2$，周期为 $6$（$2^6\equiv1\pmod 9$），所以最多 $2+6=8$个不同的值. 抽屉原理只能说明循环存在，求不出循环从哪里开始、有多长；要计数，就要看分母.

3. 二进制视角. 把 $x_0$写成二进制小数 $0.d_1d_2d_3\cdots$，乘 $2$取小数部分就是把各位数字左移一位. 第 6 题中 $x_{2021}=x_0$等价于二进制小数以 $2021$为周期，循环节有 $2^{2021}$种，去掉全为 $1$的那一种（对应 $x_0=1\notin[0,1)$），共 $2^{2021}-1$个，与前面的结果一致，可作验算.

4. 书写要点.

• 整数数列直接写模 $36$的同余式即可，不必换元成小数；同时说明各项落在一个完全剩余系中，同余才能推出相等.
• 用到 $\{a\{b\}\}=\{ab\}$（$a\in\mathbf Z$）时要说明 $a$为整数.
• 计数时充要性都要说明：第 6 题中每个整数 $C\in[0,2^{2021}-1)$给出的 $x_0=\dfrac{C}{2^{2021}-1}$都满足条件，且不同的 $C$对应不同的 $x_0$.