某台函数计算器上有一个显示屏和两个操作键.如果按一下第一个操作键,则将原显示屏上的数变为 $\left[\dfrac{x}{2}\right]$($[x]$ 表示不超过 $x$ 的最大整数);如果按一下第二个操作键,则将原显示屏上的数变为 $4x+1$.按一下任意一个操作键称为一次操作.现在显示屏上的数为 $1$,问:
【难度】
【出处】
2016年全国高中数学联赛江苏省复赛(加试)
【标注】
  1. 是否可以经过有限次操作,显示屏上出现整数 $2000$?并说明理由;
    标注
    答案
    不可能出现,理由略
    解析
    不可能.
    将数字转化成二进制,那么,按第一个操作键表示将显示屏上的数的最后一位去掉;按第二个操作表示在显示屏上的数后面加上 $01$.
    当初始数为 $1$ 时,经过以上两次操作后得到的数没有两个 $1$ 相邻,而$$(2010)_{10}=(11111010000)_{2},$$其中有两个以上的 $1$ 相邻,所以显示屏上不可能出现整数 $2000$.
  2. 小于 $2000$ 的整数中有多少个数可以经过有限次操作在显示屏上出现?
    标注
    答案
    $233$
    解析
    如果先进行第二种操作,后进行第一种操作,则等于在原数后加 $1$ 个 $0$,所以在二进制中,任意一个没有两个 $1$ 相邻的数都可以经过有限次操作得到.
    故在显示屏上可以出现的小于 $2000$ 的整数的个数等价于不大于 $(10101010101)_{2}$,且没有两个 $1$ 相邻的自然数的个数.
    不含 $1$ 的自然数只有 $1$ 个;
    含有 $1$ 个 $1$ 且不大于 $(10101010101)_{2}$ 的自然数有 ${\rm C}_{11}^{1}=11$ 个;
    含有 $2$ 个 $1$ 且不大于 $(10101010101)_{2}$ 的自然数有 ${\rm C}_{10}^{2}=45$ 个;
    含有 $3$ 个 $1$ 且不大于 $(10101010101)_{2}$ 的自然数有 ${\rm C}_{9}^{3}=84$ 个;
    含有 $4$ 个 $1$ 且不大于 $(10101010101)_{2}$ 的自然数有 ${\rm C}_{8}^{4}=70$ 个;
    含有 $5$ 个 $1$ 且不大于 $(10101010101)_{2}$ 的自然数有 ${\rm C}_{7}^{5}=21$ 个;
    含有 $6$ 个 $1$ 且不大于 $(10101010101)_{2}$ 的自然数有 $1$ 个;
    综上所述,满足条件的自然数有:$$1+11+45+84+70+21+1=233$$个.
题目 问题1 答案1 解析1 备注1 问题2 答案2 解析2 备注2
0.108199s