Algorithm 版 (精华区)

发信人: sino (茶水), 信区: Algorithm
标  题: 克拉茨问题(zz)
发信站: 哈工大紫丁香 (2002年08月28日21:13:54 星期三), 站内信件

【克拉茨问题】

    50年代开始,在国际数学界广泛流行着这样一个奇怪有趣的数学问题:任意给定
一个自然数x,如果是偶数,则变换成x/2,如果是奇数,则变换成3x+1.此后,再对 得
数继续进行上述变换.例如x=52,可以陆续得出26,13,40,20,10,5,16,8,4,2,1.如果
再做下去就得到循环:
(4,2,1).再试其他的自然数也会得出相同的结果.
   上述变换,实际上是进行下列函数的迭代

{
x/2   (x是偶数)

C(x)=


3x+1  (x是奇数)

   问题是,从任意一个自然数开始,经过有限次函数C迭代,能否最终得到循环(4,
2,1),或者等价地说,最终得到1?据说克拉茨(L.Collatz)在1950年召开的一次国
际数学家大会上谈起过,因而许多人称之为克拉茨问题.但是后来也有许多人独立地
发现过同一个问题,所以,从此以后也许为了避免引起问题的归属争议,许多文献 称
之为3x+1问题.
   克拉茨问题吸引人之处在于C迭代过程中一旦出现2的幂,问题就解决了,而2的幂
有无穷多个,人们认为只要迭代过程持续足够长,必定会碰到一个2的幂使问题 以肯
定形式得到解决.正是这种信念使得问题每到一处,便在那里掀起一股"3x+1问题"狂
热,不论是大学还是研究机构都不同程度地卷入这一问题.许多数学家开始 悬赏征
解,有的500美元,有的1000英镑.
   日本东京大学的米田信夫已经对240大约是11000亿以下的自然数做了检验.
1992年李文斯(G.T.Leavens)和弗穆兰(M.Vermeulen)已经对5.6*1013的自然数进行
 了验证,均未发现反例.题意如此清晰,明了,简单,连小学生都能看懂的问题,却难
到了20世纪许多大数学家.著名学者盖伊(R.K.Guy)在介绍这一世界难题的时候,竟
 然冠以"不要试图去解决这些问题"为标题.经过几十年的探索与研究,人们似乎接
受了大数学家厄特希(P.Erdos)的说法:"数学还没有成熟到足以解决这样的问 题
!"有人提议将3x+1问题作为下一个费尔马问题.
   下面是我对克拉茨问题的初步研究结果,只是发现了一点点规律,距离解决还很
遥远.

克拉茨命题:设 n∈N,并且


{
n/2   (n是偶数)

f(n)=


3n+1  (n是奇数)

    现用f1(n)表示f(n),f2(n)=f(f(n)),...fk(n)=f(f(...f(n)...)).
    则存在有限正整数m∈N,使得fm(n)=1.(以下称n/2为偶变换,3n+1为奇变换,并
且称先奇变换再偶变换为全变换)

克拉茨命题的证明：

   引理一:若n=2m,则fm(n)=1 (m∈N)

     证明:当m=1时,f(n)=f(2)=2/2=1,命题成立,设当m=k时成立,则当m=k+1时,
fk+1(n)=f(fk(2k+1))=
              =f(2)=2/2=1.证毕.

   引理二:若n=1+4+42+43+...+4k=(4k+1-1)/(4-1)  (k∈N),则有
f(n)=3n+1=4k+1=22k+2,从而f2k+3(n)=1.

     证明:证明是显然的,省略.

   引理三:若n=2m(4k+1-1)/(4-1)      (m∈N), 则有fm+2k+3(n)=1.

     证明:省略.

    定理一:集合 O={X|X=2k-1,k∈N} 对于变换f(X)是封闭的.

   证明:对于任意自然数n,若n=2m,则fm(n)=1,对于n=2k,经过若干次偶变换,必然
要变成奇数,所以我们以下之考虑奇数的情形,即集合O的情形.对于奇数,首先要
进行奇变换,伴随而来的必然是偶变换,所以对于奇数,肯定要进行一次全变换.为了
直观起见,我们将奇数列及其全变换排列如下:

 
k
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

0
2k-1
1
3
5
7
9
11
13
15
17
19
21
23
25
27
29
31
33
35
37
39
41
43
45
47
49
51
53
55
57
59
61
63
65
67
69
71
73
75
77
79
81
83
85
87
89
91
93
95
97
99
101

1
3k-1
2
5
8
11
14
17
20
23
26
29
32
35
38
41
44
47
50
53
56
59
62
65
68
71
74
77
80
83
86
89
92
95
98
101
104
107
110
113
116
119
122
125
128
131
134
137
140
143
146
149
152

2
3k-2
1
 
4
 
7
 
10
 
13
 
16
 
19
 
22
 
25
 
28
 
31
 
34
 
37
 
40
 
43
 
46
 
49
 
52
 
55
 
58
 
61
 
64
 
67
 
70
 
73
 
76

3
3k-1
 
 
2
 
 
 
5
 
 
 
8
 
 
 
11
 
 
 
14
 
 
 
17
 
 
 
20
 
 
 
23
 
 
 
26
 
 
 
29
 
 
 
32
 
 
 
35
 
 
 
38

4
3k-2
 
 
1
 
 
 
 
 
 
 
4
 
 
 
 
 
 
 
7
 
 
 
 
 
 
 
10
 
 
 
 
 
 
 
13
 
 
 
 
 
 
 
16
 
 
 
 
 
 
 
19

5
3k-1
 
 
 
 
 
 
 
 
 
 
2
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
5
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
8
 
 
 
 
 
 
 
 

6
3k-2
 
 
 
 
 
 
 
 
 
 
1
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
4
 
 
 
 
 
 
 
 

7
3k-1
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2
 
 
 
 
 
 
 
 

8
3k-2
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
 
 
 
 
 
 
 
 

    第一行(2k-1)经过全变换(3(2k-1)+1)/2=3k-1变成第二行,实际上等于第一行
加上一个k,其中的奇数5,11,...6k-1又回到了第一行.以下各行是等差数列3k- 2,
3k-1交错排列.由于最终都变成了奇数,所以集合O对于变换f(X)是封闭的.

   定理二:任何奇自然数经过若干次变换都会变成1.

   证明:

   我们看到 奇数经过全变换变成为3k-1型数,3k-1型奇数经过全变换有一半仍然
变成3k-1型奇数,而另一半3k-1型偶数经过除以2有一半变成为3k-2型奇数,而 
3k-2型奇数经过全变换又变成为3k-1型数.换句话说不可能经过全变换得到3k-2型
数.
   下面我们只研究奇数经过全变换的性质,因为对于其他偶数经过若干次偶变换,
仍然要回到奇数的行列里来.
   我们首先证明奇数经过若干次全变换必然会在某一步变成偶数.
   设2a0-1是我们要研究的奇数,它经过全变换变成3a0-1,假设它是一个奇数并且
等于2a1-1,2a1-1又经过全变换变成为3a1-1=2a2-1,3a2-1=2a3-1,...3ak-1- 
1=2ak-1,所以a1=(3/2)a0,a2=(3/2)a1,...ak=(3/2)ak-1.
   所以最后ak=(3/2)ka0,要使ak是整数,可令a0=2kn,(n是奇数).于是ak=3kn.则从
2a0-1经过若干次全变换过程如下:
   2k+1n-1 -> 3*2kn-1 -> 32*2k-1n-1 -> 33*2k-2n-1 ->... -> 3k+1n-1 (偶数
).

   然后我们证明经过全变换变成偶数的奇数一定大于该偶数经过若干偶变换之后
得到的奇数.
   设3k+1n-1=2mh (h为奇数),我们要证明 h<2*3kn-1:
   h=(2*3kn-1+3kn)/2m<2*3kn-1,令a=3kn,b=2m-1,则有 2ab>a+b,而这是显然的.


   定义:以下我们将称呼上述的连续全变换紧接着连续的偶变换的从奇数到另外一
个奇数的过程为一个变换链.

   接着我们证明奇数经过一个变换链所得的奇数不可能是变换链中的任何中间结
果,包括第一个奇数.

   若以B(n)表示奇数n的变换次数,m是n经过变换首次遇到的其他奇数,则有

   定理三:B(n)=k+1+B(m),其中k是满足3n+1=2km的非负整数.

   证明:n经过一次奇变换,再经过k次偶变换变成奇数m,得证.
   举例来说,
B(15)=2+B(23)=2+2+B(35)=2+2+2+B(53)=2+2+2+5+1+B(5)=2+2+2+5+1+5=17

 



--
かつて、純潔な愛が俺の前に置いていたが、大切にしていなかった。あの愛を失った
、どんなに後悔したか、分かってきた！世の中に一番つらいことは、これしかないと
思う。お前の剣が、俺の喉から切ってくれよ！もう猶予しないぞ！もし、神様から、
もう一度やらせる機会がくれれば、俺は、あの男の子にそう言うのが決まっている
――愛してる！もし、この愛に期限を付けなければならなかったら、
俺の希望は：一万年！！！！    

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.239.224]