高度对称的多面体和它们的对偶多面体

正四面体、正方体、正八面体、正十二面体、正二十面体,这是古希腊人就发现的五种正多面体,它们拥有最高标准的对称性。这五种正多面体又叫做 Platonic 体,它们在古希腊的哲学观念中占据着至关重要的地位。 Leonhard Euler 发现,多面体的顶点数 V 、棱数 E 和面数 F 一定满足公式 V – E + F = 2 ,这叫做 Euler 多面体公式。利用这个公式,我们可以证明正多面体只有五种。假设一个正多面体的每个面都是正 p 边形,那么所有 F 个面一共就有 p · F 条边;每两条边拼在一起形成了一条棱,因而总的棱数就是 E = p · F / 2 。反过来, F 就应该等于 2 · E / p 。不妨再假设每个顶点处都汇集了 q 条棱,那么总的棱数似乎应有 q · V 个;但这样计算的话,每条棱都被重复算了两次,因而总的棱数实际上应该是 E = q · V / 2 。反过来, V 就应该等于 2 · E / q 。另外, Euler 的多面体公式告诉我们, V – E + F = 2 始终成立。

把上面几个式子合在一起,于是得到:

2 · E / q – E + 2 · E / p = 2

整理可得:

1/p + 1/q – 1/2 = 1/E

因此, 1/p + 1/q 一定大于 1/2 。但是,正多面体每个面至少都有三条边,每个顶点也至少汇集了三条棱,因此 p 和 q 都是大于等于 3 的整数。要想 1/p + 1/q > 1/2 ,只有以下五种可能:

  1. p = 3 , q = 3
  2. p = 3 , q = 4
  3. p = 4 , q = 3
  4. p = 3 , q = 5
  5. p = 5 , q = 3

这正好对应于那五种正多面体。最近 Localhost-8080 沉迷于折纸,我也因此学习了不少与多面体相关的东西。想不到,这些看似老生常谈的东西,里面的水可深着呢。这五种正多面体表面上只是问题的五个不同的解,但互相之间却有着出人意料的联系。我们再列一个更加完整的表格,有意思的东西会慢慢呈现出来:

名称 面数 F 顶点数 V 棱数 E 每个面的边数 p 每个顶点处的棱数 q
正四面体 4 4 6 3 3
正方体 6 8 12 4 3
正八面体 8 6 12 3 4
正十二面体 12 20 30 5 3
正二十面体 20 12 30 3 5

Read more…

趣题:用两枚硬币随机生成 1 到 n 之间的整数

为了随机地并且概率均等地生成一个 1 到 6 之间的整数,通常的做法就是抛掷一个正方体的骰子。不过,这并不是唯一的办法。如果你有一枚公正的、正反概率相同的硬币,以及一枚不公正的、正反概率之比为 1 : 2 的硬币,那么你也能概率均等地生成一个 1 到 6 之间的整数。首先抛掷那枚不公正的硬币,那么结果有 1/3 的概率是正面朝上,有 2/3 的概率是反面朝上。如果出现了正面朝上的情况,那么令 i = 1 ;如果出现了反面朝上的情况,那么就再抛掷那枚公正的硬币,掷出正面则令 i = 2 ,掷出反面则令 i = 3 。最后,再抛掷一次公正的硬币,如果正面朝上则令 j = 0 ,如果反面朝上则令 j = 3 。容易看出, i + j 的值有 1, 2, 3, 4, 5, 6 这六种可能,它们出现的概率是均等的,都是 1/6 。

有人或许会说,用硬币模拟骰子哪有那么复杂,只用一枚公正的硬币就能办到:连续抛掷三次硬币,并且规定掷出“正正正”代表数字 1 ,掷出“正正反”代表数字 2 ,“正反正”为 3 ,“正反反”为 4 ,“反正正”为 5 ,“反正反”为 6 ,掷出“反反正”和“反反反”则重来,这不就行了吗?不过,这种方法有一个局限性:它不能保证整个过程在有限步之内完成。而我们刚才的方法中,总的步骤数有一个上限:三步之内必然完成。

我们的问题是:是否对于所有的正整数 n ,都能找到两枚合适的硬币,使得借助它们便能在有限步之内概率均等地产生一个 1 到 n 之间的整数?

Read more…

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

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

Read more…