Thue-Morse 序列与免平方字符串

字符串 hello 当中连续出现了两个 l 。字符串 prototype 当中连续出现了两个 ot 。字符串 nonsense 当中连续出现了两个 nse 。如果某个字符串中连续出现了两个相同的片段,换句话说这个字符串里面含有形如 XX 的模式(其中 X 代表一个子串),我们就说这个字符串中含有一个“平方”(square)。如果某个字符串中没有平方出现,我们就说这个字符串是“免平方”的(square-free)。

如果只使用两种字符,比方说字符 0 和字符 1 的话,我们只能构造出一些长度非常有限的免平方字符串。事实上,我们只能构造出以下 6 个免平方字符串: 0 、 1 、 01 、 10 、 010 、 101 。然而,如果允许使用三种字符,比方说字符 0 、 1 、 2 的话,我们不但能够构造出任意长的免平方字符串,还能构造出无限长的免平方字符串。在继续阅读下去之前,你不妨先自己试试看。

Read more…

为什么Fibonacci数列相邻两项之比会趋于0.618?

    你或许熟知一个非常经典的结论: Fibonacci 数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … (头两项都是 1 ,此后每一项都是前两项之和)的相邻两项之比将会越来越接近黄金比例 0.618 ,不信请看:

      1 / 1 = 1.0000000…
      1 / 2 = 0.50000000…
      2 / 3 = 0.66666667…
      3 / 5 = 0.60000000…
      5 / 8 = 0.62500000…
      8 / 13 = 0.61538462…
      13 / 21 = 0.61904762…
      21 / 34 = 0.61764706…
      34 / 55 = 0.61818182…
      55 / 89 = 0.61797753…
      89 / 144 = 0.61805556…
      144 / 233 = 0.61802575…
      … …

    Fibonacci 数列究竟是怎么和黄金比例扯上关系的?一个简单的解释就是,假设相邻两项之比存在一个极限,那么到了无穷远的时候,连续的三个数 a, b, a + b 将会满足 a / b = b / (a + b) ,这正好就是黄金比例的定义。我最近用 Mathematica 做了一组动画,尝试着用图形化的方法更直观地展示 Fibonacci 数列和黄金比例之间的联系。

Read more…

Hofstadter的非线性递推数列

    在著名奇书 Gödel, Escher, Bach: An Eternal Golden Braid 的第五章中,为了展现出递推序列的神奇之处,作者 Douglas Hofstadter 定义了这么一个递推序列: G(n) = n – G(G(n – 1)) ,其中 G(1) = 1 。这个序列的前 30 项如下:

n 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
G(n) 1 1 2 3 3 4 4 5 6 6 7 8 8 9 9 10 11 11 12 12 13 14 14 15 16 16 17 17 18 19

      

    这个数列通常被称作 Hofstadter G-sequence 。它有什么特别的地方呢?如上图,如果把每个标号为 n 的结点都连接到标号为 G(n) 的结点下方,这样的话你将会得到一棵树。从第二行开始算起,各行的结点个数依次为 1, 1, 2, 3, 5, 8, 13, … 正好是著名的 Fibonacci 数列(头两个数都是 1 ,从第三个数开始,每个数都是前两个数之和)。如果我们把第 i 个 Fibonacci 数记作 Fi 的话,上面的规律可以重新表述为:当 n ≥ 2 时,这棵树的第 n 行的结点总个数为 Fn-1 。另外,这棵树的前 n 行的结点总数(也就是第 n 行最右边那个结点的编号)正好等于 Fn+1 ,也是一个个的 Fibonacci 数。对照上面两个事实,你会惊奇地发现,莫非 F1 + F2 + … + Fn-1 + 1 总是等于 Fn+1 ?事实的确如此,上面这个式子对于所有大于等于 2 的正整数 n 均成立。

Read more…

Fibonacci数列性质的组合证明

    数列 1, 1, 2, 3, 5, 8, 13, 21, 34, … 叫做 Fibonacci 数列。这个数列有很多神奇的性质,其中一个性质是,每一个 Fibonacci 数的平方与它前后两个 Fibonacci 数的乘积一定正好相差 1 。具体地说,如果把第 n 个 Fibonacci 数记做 Fn ,那么有:

      Fn+1 · Fn+1 – Fn · Fn+2 = (-1)n

    今天看到了这个定理的一个组合数学证明,觉得非常有意思,在这里和大家分享。

Read more…

经典证明:Conway的士兵

    今天听说了 Conway’s Soldiers ,这是 Conway 大牛在 1961 年提出的一个数学谜题(似乎 Conway 的出镜率也太高了),我觉得非常有意思,在这里跟大家介绍一下。内容基本上来自于 Wikipedia 的相关页面

    假设有一个无限大的棋盘。棋盘上可以放置一些象征着士兵的棋子。一个棋子可以跳过并吃掉和它相邻的一枚棋子(就像孔明棋一样)。这是棋子的唯一一种移动方式。现在,在某个位置画一条无限长的水平线,你需要在水平线下面放置足够多的棋子,使得它们前仆后继地往水平线上方跳,最终能够跳到水平线以上 n 个单位的位置。

      

    如图所示,当 n = 1 时,两个棋子就够了。当 n = 2 时,我们需要 4 个棋子。当 n = 3 时,最少需要 8 个棋子。

Read more…