经改遍的自我指涉数列题
最近我坐在第一排，所以老师上课发卷子+擦黑板的时候在我看来就如同下雪一般……还有20天高考～兴奋兴奋！
前两个星期数学在做京卷，看来老师是希望能够挖点什么信息素出来。当我刷卷子时候，有一道数列填空题吸引了我的注意——因为他竟然是自我指涉的！这与《GEB》的精神不谋而合。题目中定义的数列是这样的：“在数列a0,a1,a2,a3,a4中，ak的值表示数字k在这个数列里面出现的次数。求a4=( )，a0+a1+a2+a3=( )。”这个数列和我们平时接触烂了的等B等X完全不一样。首先，有一个很基本的结论需要我们去发现：a0+a1+a2+a3+a4=5。为什么呢？因为每个ai代表的是他的序号i出现的次数，那么累加起来就是0~4的“出现次数”——当然可以有出现0次的数字，由于一共只有5个位子，所以说所有数字出现的总次数就肯定是5了。那么剩下的就好办了，a4=0,a0+a1+a2+a3=5。这个数列是唯一的，即 2,1,2,0,0.
然后我自然想到了另一个问题：对于什么样子的n，能够让我们构造出满足上述性质的数列a0,a1,a2,…,an？即：求所有的n，使得可构造数列a0,a1,a2,…,an，并且满足ak的值表示数字k在这个数列里面出现的次数，并且给出所有可能的构造方式。我对于n<=6时尝试了一下，发现只有4和6可以——这里面有什么规律吗？下晚自习的时候我告诉了Malloc，然后他解决了一半，我解决了另一半——其实这个问题不是很难，但是靠两个人做出来的显得有点难。你能想出来吗？
答案：Malloc做的那一半就是给出了一个构造的方法，而我的这一半就是证明了他的方法是唯一的。他的构造方法如下：对于所有的n>=6，令a0=n-3,a1=2,a2=1,a[n-3]=1，其余的都等于0.这个结果是正确的，大家可以自行验证下。那么如何证明这个构造的方法是唯一的呢？为了叙述和排版好认些，不妨设a0=k,a1=m，那么由基本性质可知整个数列中还有m个数是等于1的，k个数是等于0的。那么剩下的未知的空位还有n+1-m-k-2个或n+1-m-k-1个或n+1-m-k个——由于m与k不能同时等于1，所以n+1-m-k个的情况就首先被排除了。我们就空位还有n+1-m-k-2个的情况——即m和k都不等于1或0——进行讨论， n+1-m-k-1个的情况讨论方法类似。这个数列有一个我在上文简单地证明了的性质：a0+a1+…+an=n+1。那么现在我们已经能够确定的和值是k+m+m，即a0+a1+另外m个1，那么剩下的数列成员的和值就是n+1-k-2m。因为多出来的空位既不能是0，也不能是1，那么他们必定都大于等于2。结合空位数量与总和的关系，我们就可以得出这样的不等式：2*(n+1-m-k-2)<=n+1-k-2m，化简就能得到一个对我们非常有利的结论：k>=n-3。那么剩下的事情就是证明k>=n-2时无法构造了。这是个简单的问题，因为当a0>=n-2时，a[n-2]>=1，那么a1>=2，加起来，你就会发现a0+a[n-2]+a[1]=n+1，可是注意之前的a[a1]是不等于0的，那么和值就超过了n+1。所以，对于空位还有n+1-m-k-2个的情况，我们得到了Malloc的构造是唯一的。
本文由 严酷的魔王 创作，转载或引用前请联系我们。
标签：数列, 自我指涉