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

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

题目1 （2013年高联二试）给定正整数 𝑢,𝑣．数列 {𝑎_(𝑛)} 定义如下： 𝑎_(1)=𝑢+𝑣，对整数 𝑚≥1， 公式：a_{2m}=a_m+u; a_{2m+1}=a_m+v．记 公式：S_m=a_1+a_2+\cdots+a_m(m=1,2,\cdots)．证明：数列 {𝑆_(𝑛)} 中有无穷多项是完全平方数．

题目2 （2010年IMO预选题）数列 𝑥_(1),𝑥_(2),⋯ 定义如下： 公式：x_1=1,x_{2k}=-x_k,x_{2k-1}=(-1)^{k+1}x_k(k\geq1). 证明，对于所有的 𝑛≥1,𝑥_(1)+𝑥_(2)+⋯+𝑥_(𝑛)≥0.

题目3 数列 {𝑥_(𝑛)}_(𝑛≥1) 定义如下：

公式：x_{1}=1,x_{2n}=1+x_{n},x_{2n+1}=\frac{1}{x_{2n}}

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

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

于是𝑢的个数就等于下标的二进制中0的个数加1；𝑣的个数就等于下标的二进制中1的个数．我们设𝑆_(2)(𝑛)为𝑛在二进制中的数码和(即1的个数)．则有

公式：a_n=\left(\lceil\log_2(n+1)\rceil-S_2(n)+1\right)u+S_2(n)v

考虑𝑆_(𝑛)=𝑎_(1)+𝑎_(2)+⋯+𝑎_(𝑛)，取𝑛=2^(𝑘)−1时，𝑆_(𝑛)可以简单表达为

公式：\begin{align*} S_{2^k-1}=&\sum\limits_{i=1}^{2^k-1}a_i\\ =&(2^k-1+T_0)u+T_1v \end{align*}

其中𝑇_(𝑖)为0到2^(𝑘)−1的二进制表示中，𝑖的总个数．容易得到𝑇_(1)=𝑘⋅2^(𝑘−1)，也可分二进制的位数计算出𝑇_(0)=(𝑘−2)⋅2^(𝑘−1)+1．

于是

公式：\begin{align*} &S_{2^k-1}\\ =&(2^k-1+(k-2)2^{k-1}+1)u+k\cdot 2^{k-1}v\\ =&(u+v)\cdot k\cdot 2^{k-1} \end{align*}

要使得𝑆_(2^(𝑘)−1)为完全平方数，取𝑘=2(𝑢+𝑣)⋅𝑡^(2)，并让𝑡取遍全体正整数即可，于是数列 {𝑆_(𝑛)} 中有无穷多项是完全平方数．

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

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

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