45 道 Bongard 问题:寻找图形分类的依据

如果让你设计一种用于人工智能测试的谜题,你会怎么设计?俄国计算机科学家 Mikhail Moiseevich Bongard 在 1967 年出版的 Проблема Узнавания 一书中提出了一种“图形分类依据”型的谜题。谜题的规则很简单:现已按照某种依据把 12 张图片分成了左右两组(每组各 6 张),问依据是什么。在 Проблема Узнавания 的附录中, Bongard 自己出了 100 道题,并把它们依次编号为 1, 2, 3, …, 100 。很多题目对于人类来说非常简单,分类依据几乎是一目了然;但是,要想设计某种算法让计算机自动解出,则是一件看上去几乎不可能完成的任务。下面这张图是书上第 283 页的三个谜题。第 7 号谜题的答案是,左边的图形都是竖着的,右边的图形都是横着的;第 8 号谜题的答案是,左边的图形都在右边,右边的图形都在左边;第 9 号谜题的答案是,左边的图形都是平滑的线条,右边的图形都是波浪形线条。

Read more…

趣题:竞技场里的狮子能否保证抓住最高速度相同的小明?

小明和狮子同被关在一个半径为 10 米的竞技场里,狮子位于竞技场的圆心处,小明则在距离圆心 1 米的地方。两者的最大运动速度都是每秒 1 米。狮子有没有什么必胜策略,使得不管小明怎么跑,它总能在有限的时间里抓住小明?

根据 MathWorld 相关词条的描述,这个问题是由 R. Rado 在 1925 年时提出的。一个经典的“答案”是,狮子只需要始终保持自己与小明在圆盘的同一半径上即可。直觉上看,由于狮子总是处在“内圈”上,因而不管小明跑到了哪里,狮子总能轻松地与小明继续保持在同一半径上;并且,狮子总有足够的余力向小明靠近,严格减小它与小明之间的距离,除非小明是沿着半径方向径直向外跑。由于竞技场的大小是有限的,小明不可能无限地向外跑,因而狮子最终总会追上小明。但是,后来人们发现,这个解法其实是错误的,原因很简单:能不断靠近小明,不一定就能在有限的时间里抓住小明,正如 1/2 + 1/4 + 1/8 + 1/16 + … 永远不会超过 1 一样。最终, A. S. Besicovitch 为小明构造出了一个极其巧妙的策略,使得狮子无论如何都抓不到小明,从而完美地解决了这个问题。不过, MathWorld 的词条里并没有提到这个解法。你能想到这个解法吗?

Read more…

寻找相邻两项之比不趋于 1.618 的广义 Fibonacci 数列

大家或许知道 Fibonacci 数列 1, 1, 2, 3, 5, 8, … 有一个非常漂亮的性质:数列中的相邻两项之比将会越来越接近黄金比例 (1 + √5) / 2 ≈ 1.618 。事实上,如果我们用 F(n) 来表示第 n 个 Fibonacci 数的话,那么当 n → ∞ 时,我们有 F(n + 1) / F(n) → (1 + √5) / 2 。

不过,可能有人并不知道,如果把 Fibonacci 数列的前两项换成两个其他的正整数(但保持 Fibonacci 数列的递推关系不变),由此所得的广义 Fibonacci 数列当中,相邻两项之比仍然会趋近于 (1 + √5) / 2 。比方说,如果数列的前两项为 7, 2 ,那么整个数列的前 15 项以及相邻两项之比的情况如下:

7, 2, 9, 11, 20, 31, 51, 82, 133, 215, 348, 563, 911, 1474, 2385, …
 
2 / 7 = 0.28571429…
9 / 2 = 4.5
11 / 9 = 1.2222222…
20 / 11 = 1.8181818…
31 / 20 = 1.55
51 / 31 = 1.6451613…
82 / 51 = 1.6078431…
133 / 82 = 1.6219512…
215 / 133 = 1.6165414…
348 / 215 = 1.6186047…
563 / 348 = 1.6178161…
911 / 563 = 1.6181172…
1474 / 911 = 1.6180022…
2385 / 1474 = 1.6180461…

更神奇的是,即使最前面这两个数当中有一个负数或者都是负数,相邻两项之比的趋势依旧不变!举个例子,若数列的开头两项是 20 和 -13 ,则有:

20, -13, 7, -6, 1, -5, -4, -9, -13, -22, -35, -57, -92, -149, -241, …
 
(-13) / 20 = -0.65
7 / (-13) = -0.53846154
(-6) / 7 = -0.85714286
1 / (-6) = -0.16666667
(-5) / 1 = -5
(-4) / (-5) = 0.8
(-9) / (-4) = 2.25
(-13) / (-9) = 1.4444444
(-22) / (-13) = 1.6923077
(-35) / (-22) = 1.5909091
(-57) / (-35) = 1.6285714
(-92) / (-57) = 1.6140351
(-149) / (-92) = 1.6195652
(-241) / (-149) = 1.6174497

事实上,不管数列的开头两项是多么奇怪的两个实数(比如 -7/2, √2, … 或者 π/10, -√e, … 等等),按照 Fibonacci 式的递推关系算出后面各项,相邻两项之比几乎总会趋于 (1 + √5) / 2 !注意,刚才我们使用了“几乎”一词,因为这个结论其实并不总是成立。今天的题目就是:请你找出至少一个反例。也就是说,你需要找出至少一个由递推关系 a(i) = a(i – 1) + a(i – 2) 生成的数列,使得当 n 趋于无穷大时 a(n + 1) / a(n) 并不趋于 (1 + √5) / 2 。

对了, 0, 0, 0, 0, 0, … 这种情况自然不算。

Read more…