数列具有遍历性的一个命题
撰文/大罕
定义1:如果数列Bn=(b1,b2,…,bn)
(n≥3,bi
是正整数)是一个对模n的简化剩余系,即Bn各项被n除的余数恰是0,1,2,
…,n-1的一个全排列,就称数列Bn具有遍历性.
定义2:数列Bn每相邻两项之差组成的数列称为数列Bn的生成数列,记为Rn-1=(r1,r2,…,rn-1)(其中ri=bi+1-bi).
显然,数列Bn与其生成数列Rn-1之间有如下关系:
bj-bk
=∑[1≤i≤j-k]ri
(其中1≤k<j≤n)
问题:当n为不小于4的偶数时,生成数列
Rn-1=(n/2-1, n/2-1, …, n/2-1, n/2, n/2+1, n/2+1, …,
n/2+1)
(注:此数列的前n/2-1项为n/2-1,中间一项为n/2,后n/2-1项为n/2+1)
所确定的数列Bn具有遍历性.
以下是我的证明:
证明:分三种情况加以证明bj≡bk
(mod n)是不可能的,均用反证法.
⑴当1≤k<j≤n/2时,假设bj≡bk
(mod n),则
bj-bk
=∑[1≤i≤j-k](n/2-1)=(j-k)(
n/2-1)≡0(mod n),
先证明( n/2-1,n)=1,即(
n/2-1)与n互质,
假设( n/2-1,n)=d
(d>1),即(
n/2-1)与n有公约数d,
则d| n 且d|
(n/2-1),
设n=2tpxpy…pz,则n/2-1=2t-1pxpy…pz-1,
由d| n 知,d=2t´px´py´…pz´(其中t´<t,x´≤
x,y´≤ y,…,z´≤z,且均为正整数,)
再由d| (n/2-1) 知,d=2t´px´py´…pz´|(2t-1pxpy…pz-1),这显然是不可能的!所以(
n/2-1,n)=1获证.
由(j-k)(
n/2-1)≡0(mod n)和 (
n/2-1,n)=1可知,
n| (j-k),但由1≤k<j≤n/2得1≤j-k<( n/2-1),
而( n/2-1)<n,从而说明n| (j-k)是不可能的.证毕.
⑵当n/2<k<j≤n时,假设bj≡bk
(mod n),则
bj-bk =(j-k)(n/2+1)≡0(mod n),
用类似⑴的方法,可证明这也是不可能的.
⑶当1≤k≤n/2<j≤n时,假设bj≡bk
(mod n),则
bj-bk =∑[1≤k≤j-k]ri
=(n/2-k)(n/2-1)+n/2++(j-n/2-1)(n/2+1)
≡(n/2)(j-k)+(j+k-1)
≡0 (mod
n),
当j-k为偶数时,
bj-bk≡(n/2)(j-k)+(j+k-1)
≡j+k-1
≡0 (mod n),
这说明n|j+k-1,但n是偶数而j+k-1是奇数,所以这是不可能的;
当j-k为奇数时,令j-k=2q-1(q=1,2,…,n/2),则
bj-bk≡(n/2)(2q-1)+(j+k-1)
≡j+k-1-n/2
≡0 (mod n),
这说明n|j+k-1-n/2,但0<j+k-1-n/2≤n-1<n,所以这也是不可能的.
综上所述,当1≤k<j≤n时,
bj≡bk (mod n)是不可能的,即数列Bn具有遍历性.
加载中,请稍候......