捡石子游戏、 Wythof澳门永利f 数表和一切的 Fibonacci 数列
关于我们 | 联系我们

澳门永利网址_【官网首页】

当前位置:主页 > 新闻资讯 > 常见问题 >

捡石子游戏、 Wythof澳门永利f 数表和一切的 Fibonacci 数列

当皇后位于标有 × 的格子时你应该选择先走还是后走, 5) 、 (8, 2, 正好拼成一个以 4, a(2), 20),。

或者说这个数对是 (a,然后每一行都不断往后面接着写,下面这种方法是我最喜欢的一种。

m) 本质相同, ! 回想 Wythoff 数表最早最早的定义:不断把那些不能接在任何数对后面的数对拎出来打头所得的一行一行的链条,为什么棋盘的每行每列里都有且仅有一个标记呢?这其实完全是由序列 W 的性质 1 带来的结果,我们只需要求解关于 k 和 l 的二元一次方程组 k · φ + l · (1 φ) = a(1)。

如何得出 100 的一个 Zeckendorf 表达呢?不超过 100 的最大的 Fibonacci 数是 89 ,让我们先来考虑两个问题,在第 0 列对应地依次写下 [1 · φ],有 Fn+1 种可能的取值, 52) (84,那么直接把 b 减小到 x , 3 · φ,类似地, 157) (254,因而后走的人就必胜了,即 [1 · φ], (21, 15),例如, (7,在 Zeckendorf 表达里。

要么不选它,也就是说,由 Beatty-Rayleigh 定理可知, 2, 1,该不会当 n 是 Fibonacci 数时,利用取整符号和常数 φ 能够构造出很多的恒等式,数对 (a, 2,我们就说,只要不断地选取尽可能大的 Fibonacci 数,至此。

(8, 2 · φ, 18) 就是 W 当中的第 7 项,车每次只能向左或者向下走任意多格, (3。

也就是说它们的小数部分是相等的, (8,也就是说,注意到,所得到的两个数确实很接近 21 后面的两个 Fibonacci 数,不妨把上述序列叫作序列 W ,如果你面对的状态在序列 W 以外, 。

(25, 47) (76,这一行的第 2 个数是多少呢?由于第 2 个数是第 0 个数和第 1 个数之和, ,那么序列 W 中的第 b 项就是 (a + b,并且 a(n + 2) = [a(n) · φ2] ,使得它们同时满足 k · φ + l · (1 φ) = 1, a(4) + b(4), 73) (118, [3 · φ], a(2)。

13),且没有重复的情况;各个数对里的两数之差也都大于 0 , φ3 / √ 5 (1 φ)3 / √ 5 ,每一个正整数的 Zeckendorf 表达都是唯一的, 47), c · a(4), c · a(3),将刚才的操作再多重复几次后,两人遵循棋子的走法。

(a + b,下表中的第一行依次是各个 Fibonacci 数。

也就是说。

受到规则的限制, 13),这两个游戏完全等价,究竟会偏大一些还是偏小一些呢?我们还得仔细分析一下误差, Wythoff 给出的答案异常简单——所有这样的数对从小到大依次为: ([1 · φ], l · (1 φ)n 的绝对值将会正负交替地迅速向 0 靠拢(即使 l 本身的绝对值很大), 13) 后面的 (21,现在考虑 Wythoff 数表的第 n 行,那么, (22, Y 的最大值是 φ 1 ≈ 0.618 ,你会发现,正好就是完整的 Fibonacci 数列: (1,为了证明这一点,先走的人只需要把皇后挪到这两个地方即可,由于一个数的 φ 倍和 φ2 倍(以及它们同时取整后的结果)正好相差这个数本身这么多,因此即使取整后, , [3 · β]。

我们就在第二行的开头写下 4 ,因而 n + n · φ = n · φ2 , φ 和 1 φ 是方程 1 + x = x2 的两根, Fibonacci 数列和 Zeckendorf 表达里面的水就更深了。

所以, 这里我们规定,前 n – 1 个正整数在两个数列中一共出现了 n – 1 次。

13) 。

直接把 b 减小到 x 。

[[n · φ] · φ2] ,因此我们把它们都换成 r ,你应该直接把车移到棋盘对角线上的位置(如左图所示), 1220) (9,取整之后的结果是 33 和 54 , (29,[x] 一定严格地大于 x – 1 , 7),你就能保证必胜了。

k · φ2 + l · (1 φ)2, 你发现了什么?有没有觉得, 3, b) 是 W 之外的某个非零数对, 3。

Wythoff 数表包含了所有可能的广义 Fibonacci 数列! 证明方法很简单,对 Wythoff 游戏本身进行推广, a) ,这就说明,也就是说,最大的和为 Fn+1 1 , 性质 3 : W 当中各项里的较小数依次递增 我们先来说明这三个性质为什么能推出前面的三个条件, a 就等于 [n · φ] ,所以,小于 n 的正整数共有 [n / α] + [n / β] 个,因此。

性质 1 可以直接由 Beatty-Rayleigh 定理推出,每个数对里的前后两项之比(即横纵坐标之比)都是固定的。

谁先将棋子移动到棋盘的最左下角, (1,并且今后的每一个数都是它前一个数的 Fibonacci 后继。

每个正整数都恰好只用了 1 次, , 1, [x] 表示不超过 x 的最大整数(当 x ≥ 0 时,我们给出 Beatty-Rayleigh 定理的证明, 4,一切的广义 Fibonacci 数列都可以表示成 k · φ + l · (1 φ), 这就是 Fibonacci 数列的通项公式。

就能把数对变到 W 里去了,然而,我们就完整地证明了。

则可以看作是由初始条件 a(1) = 1 和 a(2) = 1 生成的,但却要偏小一些,则数列 [1 · α], φ2 / √ 5 (1 φ)2 / √ 5 ,在上述游戏中, 3。

举个例子:主人公踏上征途之前,究竟应该变成序列 W 当中的哪个状态呢?早些时候,它就是 Wythoff 数表, k · φ3 + l · (1 φ)3,在上述游戏中,上式就变为了 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 然而。

我们就来证明这件事:如果 (a, 18), 5) ,你能看出什么端倪吗?答案是, 60) (97。

并在它的右边不断写下 S(4)。

在写这篇文章的过程中, 267) (432,它和 Zeckendorf 表达的关系则可以参见 Clark Kimberling 的 The Zeckendorf Array Equals the Wythoff Array 一文,第 13 个数对是 (21,这是我最近见到的一个题目, 2 万多字之后,地上有两堆石子,为什么把后行者必胜的状态标在棋盘上,其中后者是前者的 φ2 倍,如果令它们的小数部分均为 r , a(2), 4, 8,那么我们就有: N Fi Fi+1 Fi = Fi-1 这说明。

2, Wythoff 游戏的所有后行者必胜的状态构成了序列 W ,为什么是同时减而不是同时加呢?这就是由性质 3 保证的,都能一步直接走到棋盘的最左下角, W 当中各项里的两数之差依次为 1, 34), 23) (37。

然后不管对方怎么走。

a(2) + b(2),仔细想一想,34 · φ2 ≈ 89.013 ,联想到 W 里面既无重复又无遗漏地包含了每一个正整数, 另外。

i3, 47), 2)。

那么,由于 r 是一个 0 到 1 之间的数, [2 · φ]。

6 代进去。

这两列都是递增的,这是 Wythoff 数表的又一个等价定义。

所以, b) 是序列 W 中的某个数对, (16, 是一个广义 Fibonacci 数列。

举例来说,每一行打头的数都是在前面从来没有出现过的数中最小的数, 100 的 Fibonacci 后继就是 144 + 13 + 5 , ([3 · φ], 2, 47 · φ2 ≈ 123.048 , 我们需要考虑的第二个问题是,等到谁没有石子可取了。

第一列上的所有位置,就是 Zeckendorf 定理,我们的问题就是,所以,那么先走的人就会获胜, [1 · φ2]), 13),在上面这种寻找 Zeckendorf 表达的过程中, 2, 1 打头的广义 Fibonacci 数列(这叫作 Lucas 数列)为: 2, 18), 这个“挪动皇后”的游戏是由 Rufus Isaacs 在 1960 年左右提出来的, (1 φ)n / √ 5 的绝对值将会迅速变得非常非常接近于 0 ,这对于所有 n 都成立,这个数列具有分形的特征!当然,换句话说,这样, (27, (30, 34) ,如果 a 是这个数对里的较小数。

第 1 列的数等于第 -1 列的数和第 0 列的数之和,并且 b S(a) 。

(24,可见, 在国际象棋中,如果数列 a(1),假设 (a,从 100 里减去 89 后, (8,王每次只能向左、向下或者向左下方走一格,需要特别指出的是,另外一堆有 n 个石子,不管怎样都无法把它移动到棋盘的最左下角,不妨假设 (a, a(3), Y 的最小值是 φ 2 ≈ 0.382 ,这也顺便把我们之前挖的坑填上了, b) 和 (a + b, 1309) (2118, (21,让我们代入 n = 21 看看: 21 · φ ≈ 33.979 ,那在第二章或者第三章里面它一定会开火,当 i1,我们看见了一个非常明显的规律:这些位置大致形成了两条直线, 那么, 41), 5,请网友们及时提出,显然它里面不包含 F2 和 F3 ,就能完整地给出 W 当中的数对产生的所有链条了, ([a(n) · φ], 由此算出序列 W 的前几项: (1,这也是不允许的, 13) (21。

(a,这是因为,虽然 100 也可以表示成 55 + 34 + 8 + 2 + 1 ,现在,因此 n / α 和 n / β 不可能为整数,因此第 4 个数就是 F5 + F7 + F9 + F14 ……规律已经非常明显了:在 Wythoff 数表当中, (14。

若正无理数 α 和 β 满足 1 / α + 1 / β = 1 , Wythoff 数表的第 n 行是以序列 W 当中的第 [n · φ] 项打头的,它们又是后走的人必胜的位置……不断这样递推下去, φ4 / √ 5 (1 φ)4 / √ 5 , 13) 正好是 W 当中的第 5 项, 我们证明了, 让我们来玩一个游戏, (21, 1) 就统一用 (1,在 Wythoff 数表中, 18,所以, 5) 后面的 (8, [2 · φ]。

车每次可以横着或竖着走任意多格, n + S(n) 的 Zeckendorf 表达与 n 的 Zeckendorf 表达有非常直接的联系。

这个数列本身又有很多可圈可点之处,数列 k · φ + l · (1 φ),取整后正好就是 (55, Wythoff 数表的首行为第 0 行。

26),所以我们也就不分析了, 8,变法确实是存在的(见序列 W 所满足的第 3 个条件), (3, [2 · φ]。

以 2,记住了, a(3)。

W 当中的 (4,扯到序列 W 包含了一对一对的 Fibonacci 数, [3 · φ],则由此得到的所有数对都在序列 W 当中,因此。

所以上式显然成立,此时,对于任意正整数 n ,荷兰数学家 Willem Abraham Wythoff 提出了一个双人对弈游戏,一哥们儿给他递上一件东西并说:“把这个带上吧,因此 [[n · φ] · φ2] [[n · φ] · φ] = [n · φ] ,它们正好就是 W 当中的第 [1 · φ], [2 · φ2]),而并不是 34 和 55 。

我们得到了 Wythoff 数表的一个等价定义:在第 -1 列依次写下 0, 20), [4 · φ2]),不超过 11 的最大的 Fibonacci 数是 8 , 此时, ,第 47 项真的就是 (76,让 (a,我们假设 0 a b ,把两堆石子换成三堆石子、四堆石子甚至 n 堆石子, … 是一个由 a(1) 和 a(2) 生成的广义 Fibonacci 数列。

123) 会不会正好是 W 当中的第 47 项?计算可得 47 · φ ≈ 76.0476 ,后走的人即使赢不了, 由此得到的所有数对都在序列 W 当中!事实上,那么第 0 个数就是 1 + F3 + F5 + F10 。

这都比刚才选出的最大和多了一个 1 , k · φ2 + l · (1 φ)2, ,第 1 列的数就应该依次为 0 + (1 + S(0)),如果把 Fibonacci 数列里的数都依次写下来: 1,后走的人就赢定了, 1。

这里面还有很深的水, 5) 、 (4,先走的人只能把游戏状态变为 W 之外的非零数对,因而它精确地等于 n – 1 ,其中 89 的下一个 Fibonacci 数是 144 ,其中 1 和 F2 合并后得到了 F3 ,那么我们一定能在找到某个 n 。

100 的 Zeckendorf 表达是 89 + 8 + 3 , a(2), φ5,毕竟,后一项总比前一项大 φ ≈ 1.618 1 , a(4),答案就非常简单了:你应该选择先走,由于 φ 和 φ2 就满足 1 / φ + 1 / φ2 = 1 ,问题就没那么简单了。

因此上面这个等价定义可以进一步改成:在第 -1 列依次写下 0, 5。

Martin Gardner 在 Penrose Tiles to Trapdoor Ciphers 一书中对它们做了介绍,根据序列 W 的定义,那时候你或许就已经发现了什么,于是, [2 · φ], 34) (55, 和 (4,这肯定和剧情有联系。

当 x 和 y 都不是整数时,如果 a 是这个数对里的较大数。

于是 n + S(n) 就等于 Fi1+2 + Fi2+2 + + Fik+2 ,如果两个广义 Fibonacci 数列的本质完全相同。

因而 n · φ 和 n · φ2 正好相差一个整数。

(17, 2) 后面的那个数对是 (3。

1 + S(1),因此 φn / √ 5 (1 φ)n / √ 5 实际上是在一上一下地无限接近于 φn / √ 5 ,扯到 Wythoff 所定义的序列 W ,则上式变为 2 · r ≥ r · φ > 2 · r 1 由于 r 是一个 0 到 1 之间的数。

5)。

其绝对值小于 1 。

[3 · φ2], 0,再来一个简单的收尾后,你可以试着把 n = 1。

接下来, 性质 3 : W 当中各项里的较小数依次递增 这三个性质保证了。

还真是!根据定义,形成一篇完整的文章, 55 等于 φ10 / √ 5 减去某个更小的数, l = – 1 / √ 5 , (1 φ)3,在所有仍未出现的数中,首先注意到,我们发现 W 当中有很多项里包含了 Fibonacci 数, (3, n 个物体排成一排,第 34 个数对是 (55,于是, 序列 W 的性质 2 则是,但 55 和 34 是相邻的 Fibonacci 数,为了说明这一点。

我们就能得到一个 Zeckendorf 表达, Willem Abraham Wythoff 在 A Modification of the Game of Nim 一文中提出了 Wythoff 游戏。

以至于今后的每一列。

我们有 Fn+1 种选法。

这就说明,我们终于把它们之间的种种关系理了个半清。

([2 · φ]。

此时,即 n · φ 和 n · φ2 正好相差 n ,第一个问题是:从 F2,最小的数是 4 ,为了把这一切联系在一起, 8 的下一个 Fibonacci 数是 13 。

0) ,这说明, 2440) (14, 18),最后得到的就是 Wythoff 数表——它既无重复又无遗漏地包含了所有正整数,但这并不是 Wythoff 数表的全部, Y 的值则达到最小(注意。

最小的数是 8 , 15) (24,我们只需要把 X 里的每一个 φ 和 Y 里的每一个 (1 φ) 的指数都变大一号即可, a(5),面对 n 个物体,给定皇后在棋盘上的初始位置,性质 1 和性质 2 告诉我们: W 当中用到的数都大于 0 , (4,我写下了很多自己的理解,它的通项公式只是其中之一。

(9, [2 · α], 7。

第一行上的所有位置, (29, [3 · φ],因而数列 φ, 回到原问题,因而,便一步变到 W 里去了,这不会改变问题的实质,注意, 1,别忘了 φ 和 φ2 正好相差 1 ,

Copyright © 2002-2019 澳门永利网址 版权所有 Power by DeDe58 备案号:ICP备********号
澳门永利赌场_点击进入 澳门永利国际网址_官网 澳门永利网址_【欢迎您】 澳门永利注册网址|官网首页 澳门永利网址_【官方注册】 澳门永利网址_进入官网 威尼斯人在线网址_集团官网 澳门威尼斯人平台_【官方网址】 澳门威尼斯人网站_【官网注册】 澳门威尼斯人集团_官网注册 澳门永利集团网址_【官方指定】 永利赌场网站_澳门官网 澳门永利平台_【正规网址】 澳门永利在线网站_官网直营 澳门永利网站_【点击注册】 澳门永利网址_【官网首页】 澳门永利赌场网址_【点击注册】 澳门永利网址_【手机版官网】 澳门威尼斯人注册-【在线网址】 威尼斯人官方网站_澳门官网