每日一题[278] 二进制

2015年北京市北大附中高三第一次月考理科数学第20题（压轴题）：

已知数列$\{a_n\}$的项数为$n$，$a_1=a$，$a_n=1$且满足 $$a_{i+1}=\begin{cases} \dfrac{a_i}2,& 2\mid a_i,\\a_i-1,&2\nmid a_i,\end{cases}$$ 其中$i=1,2,\cdots ,n-1$．设$M(a)$表示$a_1$的取值集合，${\rm {card}}\left(M(a)\right)$表示$M(a)$的元素个数．

（1）若$n=4$，求${\rm{card}}\left(M(a)\right)$；

（2）求证：$n\leqslant a_1\leqslant 2^{n-1}$；

（3）若$a_1\leqslant 2015$，求$n$的最大值，并直接写出$n$取最大值时的${\rm {card}}\left( M(a)\right)$．

（1）解    从$a_4=1$开始往前倒推：

$a_3$的所有可能取值为$2$；

$a_2$的所有可能取值为$3,4$；

$a_1$的所有可能取值为$6,5,8$．

于是${\rm{card}} \left( M(a)\right) =3$．

（2）证明    从第（1）小题的倒推过程可以看出$a_{n-1}=2$，且如果$p \leqslant a_k \leqslant q$，其中$2 \leqslant k \leqslant n-1\land k\in\mathcal N$，那么 $$p+1 \leqslant a_{k-1} \leqslant 2q,$$ 这样倒推到首项，就有 $$n\leqslant a_1 \leqslant 2^{n-1}.$$

（3）解    如果说解决第（2）小题时我们只需要对递推过程进行上下界分析而无需具体分析变化过程的细节的话，第（3）小题就是要求我们理解递推过程的本质． 事实上，与十进制下的数除以$10$得到的结果（如果能整除的话）相当于抹去最后面的“$0$”一样（比如，$\dfrac{2310}{10}=231$），除以$2$就相当于二进制下的偶数抹去最后面的“$0$”，比如$\left( 18\right) _{10}=\left( 10010\right) _{2}$，而$\dfrac{18}{2}=9=\left(1001 \right) _{2}$． 发掘出这样的直观解释后，就可以得到项数$n$与首项$a$的关系了．由于减去$1$相当于将尾巴上的$1$改为$0$，除以$2$相当于将尾巴上的$0$抹去，因此$n$的值就是将首项$a$改写为二进制数后的数位数与为$1$的数位数之和再减去$1$，如当$a=23$时，数列$\{a_n\}$为： $$23,22,11,10,5,4,2,1$$ 共$8$项，此时$\left( 23\right) _{10}=\left( 10111\right) _{2}$，共$5$位，其中$4$个数位为$1$．

回到（3）中的特殊问题，我们知道 $$\left( 2015\right) _{10}=\left( 11111011111\right) _2,$$ 当$a \leqslant 2015$时，数位数与为$1$的数位数之和至多为$21$，因此$n$的最大值为$20$．而可以使得项数为$20$的首项$a$只可能是 $$\left( 11111011111\right) _2,\left( 11110111111\right) _2,\left( 11101111111\right) _2,\left( 11011111111\right) _2,\left( 10111111111\right) _2,$$ 共$5$个，于是${\rm{card}}(M(a))=5$．