数字生成器

一个数字生成器,生成规则如下:第$1$次生成一个数$x$,以后每次生成的结果是将上一次生成的每一个数$x$生成两个数,一个是$-x$,另一个是$x+3$.设第$n$次生成的数的个数为$a_n$,则数列$\{a_n\}$的前$n$项和$S_n=$_______;若$x=1$,前$n$次生成的所有数中不同的数的个数为$T_n$,则$T_n=$_______.


分析与解 $2^n-1$;$\begin{cases} \dfrac 12n(n+1),&n\leqslant 4,\\ 4n-6,& n\geqslant 5.\end{cases} $

关键是证明当$n\geqslant 5$时,$T_n-T_{n-1}=4$.

法一 记$P$为取相反数的操作,$Q$为加$3$的操作,例如用$PQQ$来表示数字$5$的生成操作,简记为$PQ^2$. (1) 容易知道第$n$($n\geqslant 2$)次生成数字后,所产生的数字在区间$\left[Q^{n-2}P,Q^{n-1}\right]$内,即为$[-3n+5,3n-2]$内.也就是说每次操作最多在两端各自新生成$3$个连续整数.

(2) 由于$1$模$3$余$1$,而$P,Q$操作都不能使得该操作数由不能被$3$整除的数变为能被$3$整除的,所以每次操作最多新产生$4$个数;

(3) 在第$n$次生成数字后,会在两端产生新数字$Q^{n-2}P$和$Q^{n-1}$;接下来证明$PQ^{n-2}$和$PQ^{n-3}P$也是新数字:
首先,若一个数可以通过$k$($k<n-1$)次$P$或$Q$操作生成,那么它必然不在新生成的数字之列;
其次,对于$n-2$次$P$或$Q$操作来说,$PQ^{n-3}$是所能生成的除$Q^{{n-2}}$外的最大的数,因此$PQ^{n-3}Q$和$PQ^{n-3}P$分别是$n-1$次$P$或$Q$操作所能产生的除$Q^{n-1}$和$Q^{n-2}P$以外的最大的数和最小的数.
综上所述,结论得证.

 在$n-1$次操作后,$[Q^{n-2}P,Q^{n-1}]=[-3n+5,3n-2]$中除了$3$的倍数的坑不可能填上数外,就只有两个空有待下次生成,一是$Q^{n-2}P+2$,另一个是$Q^{n-1}-2$,这两个数必须经过$n$次操作才可以产生,为$PQ^{n-2}P$与$PQ^{n-1}$,事实上,每次操作后都会留下这两个坑等待下次操作时填补.所以从第$4$次操作开始,每次操作都会产生$4$个新数.


法二 我们把每次生成过程中产生新的数的分支称为“有价值的”,可以发现规律:当$n\geqslant 4$时,所有左支在贡献一次价值之后就无法带来任何价值了.

我们可以用这种方法选出所有有价值的分支:每个新生节点(代表一个新生成的数)每发一次芽(也就是生成两个新数)后马上把它的左支砍掉.这样做的结果就是每次操作都生成$4$个新数,而这$4$个新数中只有$2$个有“繁殖”能力,它们能在下次操作用生成另外$4$个新数,这样我们就得到了通项公式.

通过这种方法,很显然“被砍掉”的数都是无价值的,下面证明新生成的数都是有价值的.

可以写出第$n$($n\geqslant 4$)次操作后新生成的$4$个数的通项公式:$$10-3n,3n-7,5-3n,3n-2.$$如果$10-3n$没有价值,设它第一次出现时对应的操作数为$m$($0<m<n$),则$10-3n$是以下$4$个数之一:$$10-3m,3m-7,5-3m,3m-2,$$于是以下$4$个等式之一成立:$$m=n,3(m+n)=17,3(n-m)=5,m+n=4,$$矛盾.因此$10-3n$有价值.类似的可以证明$3n-7,5-3n,3n-2$也有价值.

此条目发表在解题展示分类目录,贴了标签。将固定链接加入收藏夹。

发表评论