几道用二进制解决的数列问题

这是前两天给学生讲的几道数列题：

题目1 （2013年高联二试）给定正整数 ．数列 定义如下： ，对整数 ， ．记 ．证明：数列 中有无穷多项是完全平方数．

题目2 （2010年IMO预选题）数列 定义如下： . 证明，对于所有的

题目3 数列 定义如下：

这几道题的共同特征是出现了第、项与第项的递推关系．我们以题目1为例进行分析：

可以将下标用二进制表示，这样的递推关系更加简洁：即二进制末位多一个，则加；二进制末位多一个，则加．

于是的个数就等于下标的二进制中的个数加；的个数就等于下标的二进制中的个数．我们设为在二进制中的数码和(即的个数)．则有

考虑，取时，可以简单表达为

其中为到的二进制表示中，的总个数．容易得到，也可分二进制的位数计算出．

于是

要使得为完全平方数，取，并让取遍全体正整数即可，于是数列 中有无穷多项是完全平方数．

题目2和题目3也可用类似方法完成，这里就不再赘述了．

最后顺带一提，今天还给小学生讲了2012年IMO第3题的第1问，其核心思想也是利用二进制处理．

题目4 “欺诈猜数游戏”在两个玩家甲和乙之间进行，游戏依赖于两个甲和乙都知道的正整数 和 ．游戏开始时甲先选定两个整数 和 ， ．甲如实告诉乙 的值，但对 守口如瓶，乙现在试图通过如下方式的提问来获得关于 的信息：每次提问，乙任选一个由若干正整数组成的集合 （可以重复使用之前提问中使用过的集合），问甲“ 是否属于 ？”乙可以提任意数量的问题．在乙每次提问之后，甲必须对乙的提问立刻回答“是”或“否”，甲可以说谎话，并且说谎的次数没有限制，唯一的限制是甲在任意连续 次回答中至少有一次回答是真话．在乙问完所有想问的问题之后，乙必须指出一个至多包含 个正整数的集合 ，若 属于 ，则乙获胜：否则甲获胜．

证明：（1）若 ，则乙可保证获胜；（2）对所有充分大的整数 ，存在整数 ，使得乙无法保证获胜．