当前位置:首页 » 极速3d彩票 » 正文字体大小:

捡石子游戏,Wythoff数表和一切的Fibonacci数列


让我们来玩一个游戏。把某个国际象棋棋子放在棋盘上,两人跟随棋子的走法,轮流移动棋子,但只能将棋子往左方,上面或者左下方移动。谁先

将棋子放置到棋盘的最左下角,谁就获胜。如果把棋子放在所示位置上,那么你愿意先走还是后走?知道,答案与我们放的是什么棋子有关。这个游戏对于兵来说是没有意义的。在如图所示的地方放马或者放象,不管怎样都无法把它移动到棋盘的最左下角,所以我们也就不分析了。因此,我们只

在国际象棋中,车每次可以横着或竖着走任意多格。在上述游戏中,受到规则的限制,车只能只能向左或者向下走任意多格。如果问题中的棋子是车,答案就非常简单了:你应该选择先走。你应该直接把车移到棋盘对角线上的位置(如左图所示),然后

在国际象棋中,王每次可以横着,竖着或者斜着走一一个,不管别人怎么走,你都把它移回到棋盘的对角线上。这样,你就能保证必胜了。格。在上述游戏中,受到规则的限制,王每次只能向左,向下或者向左下方走一格。如果问题中的棋子是王,分析出问题的答案也不算太难:你应该选择先走。你应该直接把王移到棋盘的“奇格”里(如右图所示),然后不管对方怎么走,你都可以把它再次移到某个“奇格”里。这样,你就能保证必胜了。

在国际象棋中,皇后每次可以横着,竖着或者斜着走任意多格。在上述游戏中,受到规则的限制,皇后每次只能向左,向下或者向左下方走任意多格。如果问题中的棋子是皇后,那么你应该选择先走还是后走呢?这次,问题就没那么简单了。

这个“挪动皇后”的游戏是由Rufus Isaacs在1960年左右提出的。。给定皇后在棋盘上的初始位置,如何判断出谁有必胜策略呢?Isaacs指出了一个分析方法。

首先,第一行上的所有位置,第一列上的所有位置,以及对角线上的所有位置,可以一步直接走到棋盘的最左下角。我们可以从最左下角的位置出发,画出三条射线,把这些位置全都划掉。如果皇后位于被划掉的位置上,那么先走的人就会获胜。此时,棋盘上出现了两个死角。如果皇后在这两个地方,先走的人不得不把皇后挪到刚才被划掉的位置上,由此后走的人就必胜了。因此,从这两个地方出发,画出三条射线,被划掉的位置又是先走的人就会获胜的位置,先走的人只需要把皇后挪到这两个地方即可。此时,棋盘上又会出现两个新的死角,它们又是后走的人必胜的位置……不断这样递推下去,我们可以分析出,皇后在某个地方时先走的人必胜,皇后在某个地方时后走的人必胜。之前我们曾问,当皇后位于标有×的格子时你应该选择先走还是后走,现在我们就知道答案了:你应该后走才对。

那么,在“挪动皇后”的游戏中,什么位置是

画出尺寸的棋盘,将刚才的操作再多重复多次后,我们看见了一个非常明显的规律:这些位置大致是形成了两条直线。再仔细观察,你会发现,每行每列里恰好有一个这样的位置。有没有什么公式不用递推能够找到这些位置呢?它们为什么会形成这么两条直线呢?为什么每行每列里有且仅有一个这样的位置呢?看来,这里面还有很深的水。

令Isaacs万万没有想到的是,这个游戏虽然是他发明1907年,荷兰数学家Willem Abraham Wythoff提出了一个双人对弈游戏,后来有人把它叫作Wythoff游戏。游戏规则是这样的。地上有两堆玩家轮流取走石子,规定每次从其中一堆石子中取走任意多个石子,或者从两堆石子中马丁·加德纳(Martin Gardner)认为,Wythoff本人甚至也不是这个游戏最早的发明者-其实,实际上,取到相同的数量的石子。等到谁没有石子可取了,谁就输了。

容易研磨,Wythoff游戏和“挪动皇后”是完全等价的。把棋盘从下到上各行依次标为0 ,1,2,3,…,把棋盘从左到右各列依次标为0,1,2,3,…,那么皇后移动时坐标变化的规则,正好与Wythoff游戏中两堆石子数量变化的规则是相同的。而两个游戏的目标也是相同的:谁先将游戏状态变成(0,0),谁就获得胜利。因此,这两个游戏完全等价。

由于状态(m ,n)和(n,m)本质上相同,因此我们可以把游戏状态设定为无序数对,并约定在书写时总把另外的数写在前面。而,向前(1,2)和(2,1)就统一用(1,2)来表示了。另外,只要数对里面至少有一个数不为0,我们就说这是一个非零数对。我们的问题就是,其中非

Wythoff给出的答案异常简单-所有这样的数对从小到大依次为:

([1 · φ],[1·φ 2 ]),([[2 · φ],[2·Φ 2 ])),([3 · φ],[3·Φ 2 ]),([4 · φ],[4·φ 2 ]),…

其中φ=(√ 5 + 1)/ 2,[x]表示不超过x的最大整数(当x≥0时,[x]可以简单地理解为取x的整体部分)。不妨碍把上述序列称为作序列W。稍作计算可知,序列W的前几项为:

(1、2 ),(3、5),(4、7),(6、10),(8、13),…

对照前面那个棋盘图,我们可以看到,序列W还真挺靠谱。Wythoff证明了,序列W确实就是正确的答案,这是因为序列W满足以下三个条件:

  • 条件1:W当中的任何一个数对都无法一步变成(0,0)
  • 条件2 :W当中的任何一个数对都无法一步变成W当中的另一个数对
  • 条件3:W之中的任何一个非零数对都可以一步变成(0,0)或W当中的某一个数对

这样的话,当游戏状态为W当中的数对时,先走的人只能把游戏状态变成W之外的非零数对,后走的人即使赢不了,也总能把游戏状态移回到W当中。不断因此,如果序列W真的满足上述三个条件,刚才的公式就是正确的了。那么,序列W为什么满足上述三个条件呢?Wythoff进一步指出,这是因为序列W满足以下三个性质:

  • 性质1:W里面正好既无重复又无遗漏地包含了每一个正整数
  • 性质2:W当中其中里的两数之差依次为1,2,3,…
  • 性质3:W相互之间的里的若干数顺序转换

我们先来说明这三个性质为什么能推出前面的三个条件,然后再来说明这三性质1和性质2告诉我们:W其中用到的数都大于0,且没有重复的情况;各个数对里的两数之差也都大于0,而且也没有重复的情况。这能立即启动前面的条件1和条件2。现在,假设(a,b)是W之外的某个非零数对。如果a = 0或者a = b,那么(a,b )可以直接变成(0,0)。接着,我们假设0 <a <b。由性质1可知,在W中,有且仅有一个数对用到了一个这个数。如果a是这个数对例如,(7,12)里里的数,或者说这个数对形如(x,a),那么直接把b对准到x,一步就把(a,b)变到W里去了。是W之外的数对,把它变成(4,7),便一步变到W里去了。如果a是这个数对里的少数数,或者说这个数对是(a,x)呢?若b比x大,直接把b插入到x,同样能一步把(a,b)变到W里去。若b比x小,则说明和(a,x)近似,(根据性质2,在序列W当中,这个差值在(a,x)之前曾经出现过。所以,让(a,b)的两个数同时减小相同的量,可以把数对变到W里去了。为什么是同时减而不是同时加呢?这就是由性质3保证的。暗示来说,(6,11),(6,12) ,(6,13),…可以一步一步(6,10),而(6,7),(6,8),(6,9)则能分别变成(1,2),(3 ,5) ,(4,7)。

接下来,我们来证明序列W满足这三个性质。性质1可以直接由Beatty-Rayleigh定理推出。Beatty-Rayleigh定理说的是,若正无理数α和β满足1 /α+ 1 /β= 1,则数列[1 · α],[2 · α],[3 · α],…和[1 · β],[2 · β],[3 · β],……既无重复又无遗漏地包含了所有的正整数。由于φ和φ 2 就满足1 /φ+ 1 /φ 2 = 1,所以序列W里的所有数既无重复又无遗漏地包含了所有

为了保持文章的长度,我们称为Beatty-Rayleigh定理的证明。Beatty-Rayleigh定理有很多证明方法,下面这种方法是我最喜欢的一种。首先注意,如果x和y都不是整数,那么[x]严格地小于x,[y]严格地小于y,从而[x] + [y] <x + y。另外,[x]一定严格地大于x – 1, [y]一定严格地大于y – 1,从而[x] + [y]一定严格地大于y + 2 –2。这说明,当x和y都不是整数时,[x] + [y]将介

回到原问题。明显,在数列[1 · α],[2 · α],[3 · α],…中,小于n的正整数有[n / α]个。,,在数列[1 · β],[2 · β],[3 · β],…中,小于n的正整数有[n / β]个。因此,在这两个数列中,小于n的正整数共有[n / α] + [n / β]个。由于α和β都是无理数,因此n /α和n /β不可能是整数,由刚才的谎言,[n / α] + [n / β]一定位于n /α+ n /β– 2和n /α+ n /β之间,即n – 2和n之间。但是,[n / α] + [n / β]是个整数,因此它精确地等于n – 1。

这说明,前n – 1一个是正​​整数在两个数列中一共出现了n – 1次,这对于所有n都成立。于是,正整数1必须且只能出现在其中一个数列中,正整数2必须且只能出现在其中一个

序列W的性质2则是,W其中一部分里的两数之差依次为1,数列中,以此类推,每一个新的正整数都必须且只能出现在其中一个数列中。 2,3,…,由此第n个数对里的两数之差恰好为n。这一点也是很容易研磨来的。由于φ满足1 +φ=φ 2 ,因此n + n·φ= n·φ 2 ,即n·φ和n·φ 2 正好相差n。如果两个数正好相差n,那么这两个数的证明证明了序列W满足性质2。

序列W的性质3则是,W其中大部分的里数多个顺序递增,即[1 · φ],[2 · φ] ,[3 · φ],…依次逐次递增。这更容易了:在数列1·φ,2·φ,3·φ,…中,后一项总比前一项大φ≈1.618> 1,因此即使取注意到,性质2和性质3结合起来可以告诉我们,W其中相应的里的阻止数也是依次变换的。

至此,我们就完整地证明了,Wythoff提出的公式确实正确地指出了Wythoff游戏(也就是“挪动皇后”游戏)中后行替换胜的状态。这也顺便把我们之前挖的坑填上了。为什么把后行序列胜的状态标在棋盘上,会形成两个直线呢?看看序列W的公式,你就知道了:这是因为,每个数对里的前后重叠之比(即横纵坐标之比)都是固定的。为什么棋盘的每行每列里都有且仅有一个标记呢?这其实完全是由序列W的性质1带来的结果。

不过,故事还远远没有结束。刚才我们认为了序列W的前几项,那时候你或许就已经发现了什么。让我们再多往后写几项:[1 9659015](1、2),(3、5),(4、7),(6、10),(8、13),(9、15),(11、18),(12、20), (14,23),(16,26),(17,28),(19,31),(21,34),(22,36),(24,39),(25,41),(27 ,44),(29,47),(30,49),…

你发现了什么?有没有觉得,(1,2),(3,5),(8,13),(21, 34)这几项都都特别熟悉?没错,如果把Fibonacci数列里的数都依次写下来:

1、2、3、5、8、13、21、34,…

然后把它们两个两个成对的:

(1、2),(3、5),(8、13),(21、34),…

得到的所有数对都在序列W之中!事实上,我们还能预测出,上述数对都出现在了序列W当中的什么位置。(1,2)后面的那个数对是(3,5),它就是W当中的第2个数对;(3,5)后面的那个数对是(8,13),它就是W当中的第5个数对;(8,13)后面的那个数对是(21,34),它就是W当中的第13个数对……所以,(21,34)后面的那个数对,就应该是W当中的第34个数对咯,简单算算你会发现,嘿,还真是! ,, W当中的第34个数对为[34 · φ],[34·φ 2 ],而34·φ≈55.013,34·φ 2 ≈89.013,取整后正好就是(55,89)。你或许会猜测,该不会当n是Fibonacci数时,[n · φ]和[n·φ 2 ]一定就是后面两个Fibonacci数吧。事实上并非如此。让我们代入n = 21看看:21·φ≈33.979,21·φ 2 ≈54.979,所得到的两个数确实很接近21后面的两个斐波那契数,而要偏小一些。因此,取整之后的结果是33和54,而并不是34和55。这一切都是为什么呢?

这一切都是因为,Fibonacci数列有一个神奇的通项公式:φ n /√ 5 –(1 –φ) n /√ 5 。请注意,这个充满无理数的通项公式生成的并不是Fibonacci数的近似值,它生成的真的就是一个个的Fibonacci数。你可以试着把n = 1,2,3,4,5,6代进去,得到的值将会精确地等于1,1 ,2,3,5,8。

由于φ≈1.618,其绝对值大于1,因此随之n的增加,φ n /√ 5 的绝对值将会迅速变得非常非常大;由于1 –φ≈– 0.618,其绝对值小于1,因此导致n的增加,(1 –φ) n /√ 5 ]的绝对值将会迅速变得非常非常接近0。最终,φ n /√ 5 –(1 –φ) n /√ 5 将会无限接近于φ n /√ 5 ,一个以φ为公比的等比数列。这就解释了,为什么一个斐波那契数的

但是,用这种方法推算出来的下一个斐波那契数,实际上会偏大一些还是偏小一些呢?我们还得仔细分析一下误差。注意到1 – φ是个负数,因此可以n的增加,(194 –φ) n /√ 5 就是在正负交替地向0靠拢,因此φ n /√ 5 –(1 – φ) n /√ 5 这是在上一下地无限接近于φ n /√ 5 。的第一行依次是各个Fibonacci数,第二行是n = 1,2,3,…时φ n /√ 5 的值,第三行则是二

1 1 2 3 5 8 13 21 34 55 89
0.7236 1.1708 1.8944 3.0652 4.9597 8.0249 12.9846 21.0095 33.9941 55.0036 88.9978
-0.2764 [19659046] 0.1708 -0.1056 0.0652 -0.0403 0.0249 -0.0154 0.0095 -0.0059 0.0036 -0.0022

了,为什么34·φ和34·φ 2 正好比55和89稍大一些。34和55非常接近φ 9 /√ 5 和φ 10 /√ 5 的值,其中另一个是前者的φ倍。但34等于φ 9 /√ 5 加上某个很小的数,55等于φ 10 /√ 5 只是一些很小的数,因此34的φ倍就会比55略大一些了。34和89也都非常接近φ 9 /√ 5 和φ 11 /√ 5 的值,其中其中是前者的φ 2 倍。但34等于φ 9 /√ 5 加上某个很小的数,89等于φ 11 /√ 5 更小的数,由此34的φ 2 倍也会比89略大一些。类似地,21·φ和21·φ 2 正好比34和55稍小一些,也是因为21等于φ 8 /√ 5 有人某个很小的数,34等于φ 9 /√ 5 加上某个很小的数,55等于φ 10 /√ 5 似乎更小的数字。

这样回到了我们刚才观察到的现象:序列W中的第2个数对是(3,5),第5个数对是(8,13),第13个数对是(21,34),第34个数对是(55, 89)……我们也就算是证明了刚才提到的某些提议:把Fibonacci数列写下来,并且从(1,2)开始,每两个数组成一个数对,则必然得到所有数对都在

于是,我们挖的坑又只剩最后一个了:为什么φ n /√ 5 –(1 –φ) n /√ 5 是斐波那契

让我们把满足递推式a(n)= a(n – 1)+ a(n – 2)的数列叫作“真正的Fibonacci数列,则可以初始化是由初始条件”。a(1)= 1和a(2)= 1生成的。首先注意到,让广义Fibonacci数列里的每一项都乘上非0实数c,得到的仍然是一个广义的斐波那契数列。这,如果数列

a(1),a(2),a(3),a(4),a(5), …

是一个由a(1)和a(2)生成的广义斐波那契数列,于是

c·a(1),c·a(2),c·a(3),c·a (4),c·a(5),…

就是一个由c·a(1)和c·a(2)生成的广义Fibonacci数列。

另外,两个广义Fibonacci数列之和且必然另外,如果数列

a(1),a(2),a(3),a(4),a(5),…

是一个由a(1 )和a(2)生成的广义Fibonacci数列,和数列

b(1),b(2),b(3),b(4),b(5),…

是一个由b (1)和b(2)生成的广义Fibonacci数列,那么数列

a(1)+ b(1),a(2)+ b(2),a(3)+ b(3),a (4)+ b(4),a(5)+ b(5),…

就是一个由a(1)+ b(1)和a(2)+ b(2)生成的广义斐波那契数列。

最后,φ和1 –φ是方程1 + x = x 2 的两根,从而数列

φ,φ 2 ,φ 3。 ,φ 4 ,φ 5 ,φ 6 ,…

1 –φ,(1 –φ) 2 ,(1 –φ) 3 ,(1 –φ) 4 ,(1 –φ) 5 ,(1 –φ) 6 ,…

就成了两个非常特别的广义斐波那契数列。

把上面三点结合起来,我们将会对此做出描述:对于任意的实数k,l,数列

k·φ+ l·(1 –φ),k·φ 2 + l· (1 –φ) 2 ,k·φ 3 + l·(1 –φ) 3 ,k·φ 4 + l·(1 –φ) 4 ,…

都是一个广义的斐波那契数列。如果我们能合适的k和l,同时它们同时满足

k·φ+ l· (1 –φ)= 1,k·φ 2 + l·(1 –φ) 2 = 1

这两个方程,那么我们就相当于找到了解得k = 1 /√ 5 ,l = – 1 /√ 5 ,因而斐波那契数列实际上就是

φ/√ ] 5 –(1 –φ)/√ 5 ,φ 2 /√ 5 –(1 –φ) 2 /√ 5 ,φ 3 /√ 5 –(1 –φ) 3 /√ 5 ,φ 4 /√ 5 –(1 –φ) 4 /√ 5 ,…

这就是Fibonacci数列的通项公式。容易解释,实质上,一切的广义Fibonacci数列都可以表示成

k· φ+ l·(1 –φ),k·φ 2 + l·(1 –φ) 2 ,k·φ 3 + l·( 1 –φ) 3 ,k·φ 4 + l·(1 –φ) 4 ,…

的形式,我们只需要求解关于k和l的二元一次方程组

k·φ+ l·(1 –φ)= a(1),k·φ 2 + l·(1 –φ) 2, = a(2)

即可。因此,各种广义Fibonacci数列也将继承Fibonacci数列的很多宏观特征。比方说,产生n的增加,k·φ n 的绝对值将会迅速变得非常非常大(即使k本身的绝对值很小),l·(1 –φ) n 的绝对值将会正负交替地迅速向0靠拢(甚至l本身的绝对值很大),最终k·φ n + l·(1 –φ) n 将会一上一下地无限靠近k·φ n 。实际上,足够多个之后,一切通用Fibonacci数列都会一上一下地无限近似于一个以φ为公比的等比数列。

[

Fibonacci数列有很多每次说到Fibonacci数列时,我都喜欢讲讲Fibonacci数列的另一个神奇之处,就是Zeckendorf定理。这是由比利时数学家Edouard Zeckendorf发现的例如:100可以表示成89 + 8 + 3。我们把正整数的这种表示方法叫作它的Zeckendorf表达。注意::任何一个正整数都可以唯一地表示成若干个不相邻的Fibonacci之和。 ,,虽然100也可以表示成55 + 34 + 8 + 2 + 1,但55和34是相邻的Fibonacci数,2和1也是相邻的Fibonacci数,因此这不能算100的Zeckendorf表达。需要特别指出的是,由于F 1 和F 2 都是1,因此选了F 1 和F 3 本质上就相当于选了F 2 和F 3 ,根据规定,这也是可以的。因此,接下来,我们假设每次选1的时间的确都是F 2 ,这不会改变问题的实质。换句话说,接下来,我们假设F 1 是不能选的。

为什么Zeckendorf表达总是存在的呢?这很容易研磨来。只要不断地拾取恢复大的Fibonacci数,我们就能得到一个Zeckendorf表达。那种,如何获得100的一个Zeckendorf表达呢?不超过100的最大的Fibonacci数是89。从100里最早89后,剩下的部分是11。不超过11​​的最大的Fibonacci数是8。从11里顶端8后,剩下的部分是3,这已经是一个Fibonacci了。所以,100的Zeckendorf表达就是89 + 8 + 3。在这个过程中,我们肯定不会用到相邻的Fibonacci数。这是因为,如果正整数N相邻F i 和F i + 1 之间(其中F i 表示第i个斐波那契数),那么我们就有:

N – F i <F i + 1 – F i = F i-1

这说明,首先一个较大的Fibonacci数,结果会比小一号的Fibonacci数更小。 ,在上面这种寻找Zeckendorf表达的过程中,我们会自动地跳过所有相邻的Fibonacci数。

Zeckendorf定理真正最核心的,就是每一个正整数的Zeckendorf表达都是唯一的。为了证明这一点,让我们先来考虑两个问题。第一个问题是:从F 2 ,F 3 ,…,F n 数出几个个不相邻的数,怎样选才能让它们的和最大呢?不断把较小的Fibonacci数往大了调,你会发现,和最大的选法显然就是

F n + F n-2 + F n-4 +…

如果n是偶数,上式将会以… + F 4 + n [F](F590)或+ F 2 结束。如果n是奇数,上式将会以…+ F 5 + F 3 数与F n + 1 很接近。这是因为:

F n + 1
= F n + F n-1 [19659119] = F n + F n-2 + F n-3
= F n + F n-2 + F n-4 + F n-5
=……

不断像这样展开后,根据n的奇偶性的不同,我们要么会得到F n + F n-2 + F n-4 +…+ F 4 + F 2 + F 1 ,就是会得到F n + F n-2 + F n-4 + …+ F 5 + F 3 + F 2 。无论是哪种情况,这都比刚才选出的最大和多了一个1。也就是说,从F 2 ,F 3 ,…,F n 中选出多个个不相邻的数,最大的和为F n + 1 – 1。

我们需要考虑的第二个问题是,n个物体排成一排,从中选出几个个不相邻的物体(可以不选),一共有多少如果只有1个物体,我们要么选它,要么不选它,一共有2种选法。如果有2个物体,我们可选择这个,其中选那个,要么都不选,一共有3种选法。如此,a(1)= 2,a(2)= 3。另外,面对n个物体,满足要求的选法分为两类:如果不选最后那个物体,那就完全得看前n – 1个物体怎么选,这里面的方案数为a(n – 1);如果选了最后那个物体,那么剩下的就只能再在前n – 2个物体里选了,这里面的方案数为a(n – 2)。这说明,a(n)= a(n – 1)+ a(n – 2)。于是,数列a (1),a(2),a(3),a(4),…就是就是2,3,5,8,…。换句话说, a(n)= F n + 2

结合上面两点,我们得到了这样一个有人:从F 2 到F n 这n – 1个数中选出几个个不相邻的数(可以不选),一共有F n + 1 种选法;而这些数的总和的取值范围,则在0到F n + 1 – 1之间。所以,我们有F n + 1 种选法,有F n + 1 种可能的取值。所以,F n + 1 种选法必须得既无重复又无遗漏地取遍F ,同时,我们之前证明了,每个正整数都有至少一个Zeckendorf表达。 n + 1 种可能的取值。这就说明了,每一个正整数的Zeckendorf表达都是唯一的。

等等,我们是怎么扯到Zeckendorf表达的??让我想一想啊……哦!想起来了!想起来了!我们是从棋盘游戏,扯到与之等价的Wythoff游戏,扯到其中状态后行替换胜,扯到Wythoff所定义的序列W,扯

扯远了,扯远了。我们再把整个思路捯到了W包含了一对双的斐波那契数,扯到了斐波那契数列那著名的通项公式,最后扯到了正整数的Zeckendorf表达。 W的公式为:

([1 · φ],[1·Φ 2 ]),([2 · φ],[2·Φ 2 ]),( [3 · φ],[3·Φ 2 ]),([19437],[4· 2 ]),…

这种算术序列W的前几项:

(1、2),(3、5),(4、7),(6、10),(8、13),(9、15),(11、18),(12、20 ),(14、23),(16、2 6),(17、28),(19、31),(21、34),(22、36),(24、39),(25、41),(27、44),(29、47) ,(30,49),…

我们证明了,序列W满足以下三个重要的性质:

  • 性质1:W里面正好既无重复又无遗漏地包含了每个一个正整数
  • 类型2:W彼此之间的里数的两数之差依次为1,2,3,…
  • 性质3:W其中相互的里数的数数依次递增

这三个性质保证了,W ,我们发现W当中有很多项里包含了Fibonacci数。把它们连在一起,正好就是完整的Fibonacci数列:

(1 ,2),(3、5),(8、13),(21、34),…

其中(1、2)后面的(3、5)正好是W当中的第2项,(3 ,(5)后面的(8,13)正好是W当中的第5项,(8,13)后面的(21,34)正好是W当中的第13项,以此类推。

那么,W当中的其他项呢?仔细观察W当中的其他项,你能修剪什么端倪吗?答案是,W当中的其他项还隐藏着别的广义Fibonacci数列!比方说,W当中的

(4 ,7),(11,18),(29,47),…

正好拼成一个以4,7打头的广义Fibonacci数列!而且,(11,18)就是W当中的第7项,( 29,47)就是W当中的第18项。来猜猜看,(76,123)会不会正好是W当中的第47项?计算可得47·φ≈76.0476,47·φ 2 ≈123.048。根据序列W的定义,第47项真的就是(76,123)!

接下来,我们就来证明这件事:如果(a,b)是序列W中的某人一个数对,那么序列W中的第b项就是(a + b,a + 2b)。由于第b项里的两数之差就是b,因此我们只需要证明:如果(a,b)是序列W中的某个数对,然后序列W中的第b项的较小数就是a + b。不妨假设(a,b)是序列W中的第n项。根据序列W的定义,a就等于[n · φ],b就等于[n·φ 2 ],而第b个项的较小数则是[[n·φ 2 ]所以,我们真正只需要证明的就是:对于任意正整数n,都有[n · φ] + [n·φ 2 ] = [[n·φ 2 ]]·φ]。这本质上就是证明:

[n · φ] + [n·φ 2 ]≤[n·φ 2 ]·φ<[n · φ] + [n·φ 2 ] + 1

不妨用{x}表示x的小数部分。上式就变成了

n·φ– {n·φ} + n·φ 2 – {n·φ 2 }≤(n·φ 2 – {n·φ 2 })·φ<n ·φ– {n·φ} + n·φ 2 – {n·φ 2 } + 1

也就是:

n·φ– {n· φ} + n·φ 2 – {n·φ 2 }≤n·φ 3 – {n·φ 2 } ·φ<n·φ– {n·φ} + n·φ 2 – {n·φ 2 } + 1

然而,φ满足1 +φ=φ 2 ,也就满足n·φ+ n·φ 2 = n·φ 3 。于是,上面的不等式递增简化为

– {n·φ} – {n·φ 2 }≤– {n·φ 2 }·φ<– {n·φ} – {n·φ 2 } + 1

{n·φ} + {n·φ 2 }≥{n·φ 2 }·φ> {n·φ} + {n· φ 2 } – 1

最后,别忘了φ和φ 2 正好相差1,因此n·φ和n·φ 2 正好相差如果令它们的小数部分替换r,则上式转化

2·r≥r·φ> 2·r – 1

由于r是一个0到1之间的数,而φ≈1.618,所以上式称为成立。至此,我们就证明了,对于任意正整数n,都有[n · φ] + [n·φ 2 ]] = [[n·φ 2 ]·φ]。

利用取整符号和常数φ,我们可以构造出很多类似的恒等式。用上面的这套方法来证明这些为了说明这一点,我打算不惜文章的连贯性,在这里穿插一个习题。这是我最近见到的一个译文。讲完这个题目的解法后,我们会立即言归正正传。译文是:求证,对于任意正整数n,都有[[n · φ]·φ] = [n·φ 2 ] – 1。

解法和之前的几乎如出一辙。原等式等价于

[n·Φ 2 ] – 1≤[n · φ]·Φ<[n·Φ ] 2 ]

它又可以变成

n·φ 2 – {n·φ 2 } – 1≤(n·φ– {n ·φ})·φ<n·φ 2 – {n·φ 2 }

n·φ 2 – {n ·φ 2 } – 1≤n·φ 2 – {n·φ}·φ<n·φ 2 – {n·φ 2 }

– {n·φ 2 } – 1≤– {n·φ}·φ<– {n·φ 2 }

{n·φ 2 } + 1≥{n·φ}·φ> {n·φ 2 }

依据{n·φ } = {n·φ 2 },因此我们把它们都换成r。整个式子就变成了:

r + 1≥r·φ> r

同样地,由于r是一个0到1之间的数,而φ≈1.618,所以上式称为成立。

如果序列W当中有(a,b)和(a + b,a + 2b)这么两项,我们就说,(a + b,a + 2b)接在(a,b)后面。而我们刚才证明的实际上就是,序列W当中的第[1·φ 2 ] ,[2·φ 2 ],[3·φ 2 ],……项将会分别接在第1、2、3,…项的后面。把该接起来的数对全都接起来,我们就会得到很多链条,某种之前就已经观察到的

(1、2),(3、5),(8、13),(21、34),…

(4、7),(11、18), (29,47),…

似乎,每个链条里的数都构成了一个广义的斐波那契数列。而每个链条打头的数对,则是那些不能接在任何数对后面的数对,也就是第[1·φ 2 ],[2·φ 2 ],[3·φ 2 ],…项以外的数对。由Beatty -Rayleigh定理可知,它们正好就是W当中的第[1 · φ],[2 · φ],[3 · φ],…项。所以,我们把W当中的第[1 · φ],[2 · φ],[3 · φ],…着写成一列,再不断地写出每个数对后面然后的数对,可以完整地指向W当中的数对产生的所有链条了。联想到W里面既无重复又无遗漏地包含了每一个正整数,因此我们相当于把整个正整数排成一个无限大的数表,每个正整数都恰好只用了1次,因此数表中的每一行都是一个广义的斐波那契数列!

(1,2)–(3,5)–(8,13)–(21,34)–(55,89)–(144,233)(把这个神奇的数表叫作Wythoff数表。 –…
(4,7)–(11,18)–(29,47)–(76,123)–(199,322)–(521,843)–…
(6,10)–(16,26)–(42,68)–(110,178)–(288,466)–(754,1220)–…
(9,15)–(24,39)–(63,102)–(165,267)–(432,699)–(1131,1830)–…
(12,20)–(32,52)–(84,136)–(220,356)–(576,932)–(1508,2440)–…
(14,23)–(37,60)–(97,157)–(254,411)–(665,1076)–(1741、2817)–…
(17,28)–(45,73)–(118,191)–(309,500)–(809,1309)–(2118,3427)–…
………………

真正神奇的事情出现了。现在,我们约定,接下来说的是广义的斐波那契数列一律限定在正整数范围内。如果两个广义的斐波那契数列的实质上完全相同,只是比方说,以2,1打头的广义Fibonacci数列(这叫作Lucas数列)为:

2,1,3,4,下标被整体平移了一下,我们就认为它们俩是同一个数列。 7,11,18,29,47

它就是Wythoff数表中的第二行。接下来,我们来证明一个非常让人意识到的事实:在这个意义下,Wythoff数表包含了所有可能的广义斐波那契数列!

证明方法很简单。还记得吗,我们之前曾经获得,一切广义斐波那契数列最终都会一上一下地无限地近似于一个以φ为公比的等比数列。所以,如果a(1),a(2),a(3),…是一个广义的斐波那契数列,那么我们一定能在找到某个n,从而a(n + 1)= [a(n) · φ],并且a(n + 2 )= [a(n)·Φ 2 ]。然而,(([a(n) · φ],[a(n)·Φ 2 ])就是序列W当中的第a(n )项,它出现在了Wythoff数表的某个行里。这一行所对应的广义Fibonacci数列,本质上就是数列a(1),a(2),a(3),…。

]我们证明了一个如此优美的层次,将之前的所有东西都过渡在了一起,一切都非常漂亮地完结了。再来一个简单的收尾后,这篇文章就该结束了。毕竟,我们之前挖过………是吗?

编故事有一个非常重要的原则,叫作“契科夫之枪”(契kh夫的枪) 。说的是:如果你在第一章里提到了一块木板挂着一把一把来复枪,那在第二章或者第三章里面它一定会开火,否则它就不应该挂在那里。举个例子:主人公踏上征途之前,一哥们儿给他递上一件东西并说:“把这个带上吧,没准儿能用上……”好,这玩意儿百分之百地会被用上。如果故事片里有一个镜头专门对着播报新闻的电视,记住了,这肯定和剧情有联系。如果枪战片里

介绍文章也挂着好几把契科夫之枪的那个人来到一个大房间,四壁都是养着鱼的大水缸……呵呵,我不说你都知道一会儿会出现啥。 。比方说,刚才突然来的那个习题是怎么回事?在那个习题中,我们证明了[[n · φ]·φ] = [n·φ 2 ] – 1恒成立。好了,现在考虑Wythoff数表的第n行,它是一个广义的斐波那契数列。如果再把这个数列往前推下去,会得到什么?注意到,Wythoff数表的第n行由序列W当中的第[n · φ]项打头的。。,Wythoff数表的第n行的头两个数是[[n · φ]·φ],[[n · φ]·φ 2 ]。由于一个数的φ倍和φ 2 倍(以及它们同时取整整的结果)正好相差这个数本身这么多,因此[[n · φ]·φ 2 ] – [[n · φ] ]·φ] = [n · φ],和[[n · φ]·φ] – [n · φ] = [n·φ 2 ] – 1 – [n · φ] = n – 1。这就说明了,Wythoff数表的第n行可以估计是由n – 1,[n · φ]生成的广义斐波那契数列。所以,我们得到了Wythoff数表的一个等价定义:在第-1列依次写下0,1, 2,3,…,在第0列对应地依次写下[1 · φ],[2 · φ],[3 · φ],… ,,于是每一行里都有两个数了;在每一行里都不断往后面写下新的数,每个数都是它的前面两个数之和,最后得到的就是Wythoff数表-它既无重复又无遗漏地包含了所有正整数,也既无重复又无遗漏地包含

0 1 1 2 3 5 8 13 21 34 55 [19659046] 89
1 3 4 7 11 18 29 47 76 123 199 322
2 4 6 10 16 26 42 68 110 178 [19659046] 288 466
3 6 9 15 24 39 63 102 165 267 432 699
4 8 12 20 32 52 84 136 220 [19659046] 356 576 932
5 9 14 23 37 60 97 157 254 411 665 1076
6 11 17 28 45 73 118 191 [19659046] 309 500 809 1309
…[19659046]…

还记得Zeckendorf表达吗?然后,该该轮到它返场了!现在我们定义,把一个正整数的Zeckendorf表达里的所有Fibonacci数都往后移一位,得到的新的正整数就是原正整数的“ Fibonacci后继”。例如, 100的Zeckendorf表达是89 + 8 + 3,其中89的下一个Fibonacci数是144,8的下一个Fibonacci数是13,3的下一个Fibonacci数是5。那么,100的Fibonacci后继就是144 + 13 + 5,也就是162。我们用S(n)来表示正整数n的Fibonacci后继。刚才我们演示的就是,S(100)= 162。接下来,我们将证明这么一个例子:对于任意正整数n都有,1 + S(n)等于[(n + 1) · φ]。

如果n的Zeckendorf表达中各个Fibonacci数的下标为i 1 ,i 2 ,i 3 ,…,令

X =Φ i 1 i 2 i 3 [19659291] +…

Y =(1 –φ) i 1 +(1 –φ) i 2 +(1 – φ) i 3 +…

那么n就可以写成

X /√ 5 – Y /√ 5

由于1 –φ是一个绝对值小于1的负数,因此当i 1 ,i 2 ,i 3 ,…正好是所有人正偶数时,Y利用等比数列的求和公式可知,Y的长度是φ– 1≈0.618。对应地,当i 1 ,i 2 ,i 3 ,…正好是全体大于1的正奇数时,Y的值则达到最小(注意,在Zeckendorf表达里,Fibonacci数的下标不能取1)。利用等比数列的求和公式

为了把n变成S,可知,Y的应力是φ– 2≈– 0.382。当然,对于任意一个有限大的n来说,刚才算出的取向和对准都是取不到的。 (n),我们只需要把X里的每一个φ和Y里的每一个(1 –φ)的指数都变大一号即可。于是,1 + S(n)就可以表示为:[19659015] 1 +φ·X /√ 5 –(1 –φ)·Y /√ 5

而我们要证明1 + S(n)= [(n + 1) · φ],也就是

1 +φ·X /√ 5 –(1 –φ)·Y /√ 5 = [φ·X/√ 5 –φ·Y /√ 5 +φ]

由于等式左边的式子是一个整体,因此我们只需要证明等式右边的取整符号内的式子比等式左边的式子尺度,但不会大1或更多。这就,我们只需要证明:

0≤(φ·X /√ 5 –φ·Y /√ 5 +φ)–(1 +φ·X /√ 5 –(1 –φ)·Y /√ 5 )<1

((φ·X /√ 5 –φ·Y /√ 5 +φ)–(1 +φ·X /√ ] 5 –(1 –φ)·Y /√ 5
=(1 –φ)·Y /√ 5 –φ·Y /√ 5 +φ– 1
=(1 –2φ)·Y /√ 5 +φ– 1

是一个关于Y的一次函数,且当Y =φ– 2时函数变量1,Y =φ– 1时函数变量0。这就说明,这个一次函数的函数值永远在0和1之间。至此,我们就证到了,1 + S(n)等于[(n + 1) · φ]。

在我们之前提到了Wythoff数表的等价定义:在第-1列顺序写下0,1,2,3,…,在第0列对应地依次写下[1 · φ],[2 · φ],[3 · φ],…,然后每由于1 + S(n)等于[(n + 1) · φ],因此上面这个等价定义可以进一步改成:在第-1列依次写下0,1,2,3,…,在第0列对应地依次写下1 + S(0),1 + S(1),1 + S(2),…(这里,我们规定S(0)= 0),然后每一行都不断往后面接着写,那个每个都是都是的前面两个数之和。。

所以,第1列的数就应该依次为0 +( 1 + S(0)),1 +(1 + S(1)),2 +(1 + S(2)),…。仔细想一想,n +(1 + S(n))究竟是什么?容易观察到,n + S(n)的Zeckendorf表达与n的Zeckendorf表达有非常直接的联系。如果n等于F i 1 + F i 2 +…+ F i k ,所以S(n)就等于F i 1 +1 + F i 2 +1 +…+ F i k +1 ,于是n + S(n)就等于F i 1 +2 + F i 2 +2 +…+ F i k +2 。可见,n + S(n)的Zeckendorf表达就是n的Zeckendorf表达中所有Fibonacci数都往后移两位而得的,知道它里面不包含F 2 和F 3 ,最小的至少至少都是F 4 。因此,为了得到n +(1 + S(n))的Zeckendorf表达,我们只需要在n + S(n)的Zeckendorf表达里直接添加一个F 2 就行了。

举个例子,如果某些行的第-1个数是F 2 + F 4 + F 9 ,那么第0个数就是1 + F 3 + F 5 + F 10 ,第1个数就是F 2 + F 4 + F 6 + F 11 。那么,这一行的第2个数是多少呢?由于第2个数是第0个数和第1个数之和,因此第2个数就是F 3 + F 5 + F 7 + F 12 ,其中1和F 2 合并后得到了F 3 。类似地,由于第3个数是第1个数和第2个数之和,因此第3个数就是F 4 + F 6 + F 8 + F 13 ;由于第4个数是第2个数和第3个数之和,因此第4个数就是F 5 + F 7 + F 9 + F 14 ……规律已经非常明显了:在Wythoff数表当中,每一行的第1个数的Zeckendorf表达的最小项都是F 2 ,并且先前的每一个都是它前一个数的斐波那契后继,其Zeckendorf表达的最小项依次升级为F 3 ,F 4 ,F 5 ,…!

回想Wythoff数表首次初始的定义:不断把那些不能接在任何数对后面的数对拎出来打头所得的一行一行的链条。因此,每一行打头的数都是,前面从来没有出现过的数中最小的数。所以,我们有了一种另类的生成Wythoff数表的方式。先在第一行的开头写下1。在它的右边不断写下S (1),S(S(1)),S(S(S(1))),……此时,在所有仍未出现的数中,最小的数是4。接下来,我们就在第二行的开头写下4,并在它的右边不断写下S(4),S(S(4)),S(S(S(4))),…。此时,在所有仍未出现的数中,最小的数是6。接下来,我们就在第三行的开头写下6,并在它的右边不断写下S(6),S(S(6)),S(S(S (6))),…。此时,在所有仍未出现的数中,最小的数是8。接下来,我们就在第四行的开头写下8……不断进行下去,我们就会

另外,Wythoff数表的第-1列为0,1,2,3,……是一张Wythoff数表的另一个等价定义。 ,第0列依次为[1 · φ],[2 · φ],[3 · φ],…,这两个列都是递增的。第1列的数等于第-1列的数和第0列的数之和和。大点儿的数加上大点儿的数,和肯定也会超过,所以第1列的数也是递增的。同理,第2列,,第3列,以至于于先前的每一列,都是递增的。。是,Wythoff数表还有这么一种生成方式:在第1列从小到大列出所有Zeckendorf表达的最小项为F 2 的数,在第2列从小到大列出所有Zeckendorf表达的最小项为F 3 的数,在第2列从小到大列出所有Zeckendorf表达的最小项为F 4 的数……不断进行下去,我们就会得到一张无限大的数表,它就是Wythoff数表。这是Wythoff数表的又一个等价定义。

最后让我们回到“挪动皇后”和Wythoff游戏。Wythoff游戏的所有后行姿势胜的状态构成了序列W,它的公式为:

([1 · φ],[1·φ 2 ]),([[2 · φ],[2·φ 2 ]),([[3 · φ],[3·φ 2 ]),([4 · φ] ,[4·φ 2 ])),…

反过来,如果你面对的状态在序列W以外,那么你就是必胜的。但是,必胜的策略是什么呢?必胜的策略自然就是,把当前状态变成序列W当中的某个状态。但是,到时候你怎么才能算出,究竟应该变成序列W当中的其中状态呢?早些时候,我们证明了,变法确实是存在的(见序列W所满足的第3个条件)。但是,利用当时的证明方法,很难获得一套固定的,易实施的具体策略,可以帮助我们每次都准确地发现这个变法。毕竟,在没有高级计算器的情况下,你甚至连W里的每一个具体是多少都搞不出来。然而,最后那几个Wythoff数表的等价定义是非常离散的,这给,上述问题的解决开开辟辟一条一条新路。尺寸,我们可以立即转换,数对(a,b)在序列W当中,当且仅当a的Zeckendorf表达的最小项的下标是一个偶数,并且b = S(a)。所以,我们就有了一种判断数对是否在W当中的方法。刚才证明过恒等式1 + S(n)= [(n + 1) · φ],据此可以推出S( n – 1)+ 1 = [n · φ];于是,序列W当中的第n项就是(S(n – 1)+ 1,S(S(n – 1)+ 1))。序列W满足条件3的证明,最终导致的结果将会正好与1977年Robert Silber对Wythoff游戏的分析结果完全一致:若数对(a,b)不在序列W当中(其中0 <a <b) ,则按照上述三种情况进行分类讨论,一定能把它变成序列W当中的某个数对。三种情况分别如下:

  • 如果a的Zeckendorf表达的最小项的下标是一个奇数,则把b变成S -1 (a)。这里S -1 (x)表示把x的Zeckendorf表达里的所有Fibonacci数都往前移一位之后
  • 若a的Zeckendorf表达的最小项的下标是一个偶数,并且b> S(a),则b变成S(a)。
  • 若a的Zeckendorf表达的最小项的下标是一个偶数,并且b <S(a),那该怎么办呢?先计算出b – a的值,不妨把它记作n;然后,把(a,b)变成(S(

在写这篇文章的过程中,我看了很多资料。1907年,威廉·亚伯拉罕·怀斯霍夫(Willem Abraham Wythoff在) 1977年,罗伯特·西尔伯(Robert Silber)在Wythoff的NIM和斐波那契表示法中。文森·马丁·加德纳(Martin Gardner)在Penrose Tiles to Trapdoor Ciphers一书中对它们做Wythoff数表最早是1980年由David Morrison在Stolarsky阵列上的Wythoff对组成。一文中提出的。它和Zeckendorf表达的关系则可以看到Clark Kimberling的Zeckendorf数组等于Wythoff数组一文。与Zeckendorf表达本身有关的一些证明,尤其是Zeckendorf定理的证明,参考了和常数φ能够构造出很多的恒等式,其证明方法参考了I一文。我首先是因为看了Neil Sloane的我最喜欢的整数序列一文后,了解到Wythoff数表,才打算写这篇文章的。为了把这一切联系在一起,形成文章完整的文章,我写下了很多自己的理解,甚至有些地方的证明过程也是我自己的思考。如果有不对的地方,请网友

在数学世界里,各种数学研究对象织成一张纵横交错的大网,捡石子游戏,Wythoff数表和Fibonacci数列只是其中的三个非常小的尖端而已。2万多字之后,我们终于把它们之间的种种关系理了个半清。但是,它们各自仍然继续延伸延伸,这些恐怕再花20万字也说不完。Wythoff游戏是Nim游戏的一个变种对Wythoff游戏同时进行推广,还可以得到另一种类似的游戏。例如,把两堆石子换成三堆石子,四堆石子甚至n堆石子,提到的Wythoff数表的很多令人意向不到的等价定义和非常容易震撼的数学性质,而并非Wythoff数表的全部。例如,在Wythoff数表中,下一行的每个数的大小正好夹在上一行数的空隙之间。这背后会涉及到非常有趣的interspersion和离散理论。Wythoff数表里既无重复又无遗漏地包含了所有正整数,那么从1开始的每个正整数恰好出现在了Wythoff数表中的哪一行呢?这个问题的答案就又构成了一个数列:

0,0,0,1 ,0,2,1,0,3,2,1,4,0 、、 5、3、2、6、1、7、4…

这里我们规定,Wythoff数表的首行为第0行。这个数列本身又有很多可圈可点近似,例如删除掉数列中的第一个0,第一个1,第一个2等等,剩下的数列其实就是原数列本身。因此,这个数列具有分形的特征!当然,考察每个正整数恰恰出现在了Wythoff

Fibonacci数列和Zeckendorf表达里面的水就更深了。

http://www.matrix67.com/blog/archives/5152 ),里面就涉及到了它们之间的各种更深层的联系。


/a>

转载请注明本文地址: http://www.szantaili.com/84.html | 极速3d彩票/极速3d彩票平台/注册/官网

捡石子游戏,Wythoff数表和一切的Fibonacci数列:等您坐沙发呢!

发表评论


快捷键:Ctrl+Enter