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

正四面体、正方体、正八面体、正十二面体、正二十面体,这是古希腊人就发现的五种正多面体,它们拥有最高标准的对称性。这五种正多面体又叫做 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…

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

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

Read more…

用三段 140 字符以内的代码生成一张 1024×1024 的图片

Kyle McCormick 在 StackExchange 上发起了一个叫做 Tweetable Mathematical Art 的比赛,参赛者需要用三条推这么长的代码来生成一张图片。具体地说,参赛者需要用 C++ 语言编写 RD 、 GR 、 BL 三个函数,每个函数都不能超过 140 个字符。每个函数都会接到 i 和 j 两个整型参数(0 ≤ i, j ≤ 1023),然后需要返回一个 0 到 255 之间的整数,表示位于 (i, j) 的像素点的颜色值。举个例子,如果 RD(0, 0) 和 GR(0, 0) 返回的都是 0 ,但 BL(0, 0) 返回的是 255 ,那么图像的最左上角那个像素就是蓝色。参赛者编写的代码会被插进下面这段程序当中(我做了一些细微的改动),最终会生成一个大小为 1024×1024 的图片。

// NOTE: compile with g++ filename.cpp -std=c++11
 
#include <iostream>
#include <cmath>
#include <cstdlib>
#define DIM 1024
#define DM1 (DIM-1)
#define _sq(x) ((x)*(x)) // square
#define _cb(x) abs((x)*(x)*(x)) // absolute value of cube
#define _cr(x) (unsigned char)(pow((x),1.0/3.0)) // cube root
 
unsigned char GR(int,int);
unsigned char BL(int,int);
 
unsigned char RD(int i,int j){
   // YOUR CODE HERE
}
unsigned char GR(int i,int j){
   // YOUR CODE HERE
}
unsigned char BL(int i,int j){
   // YOUR CODE HERE
}
 
void pixel_write(int,int);
FILE *fp;
int main(){
    fp = fopen("MathPic.ppm","wb");
    fprintf(fp, "P6\n%d %d\n255\n", DIM, DIM);
    for(int j=0;j<DIM;j++)
        for(int i=0;i<DIM;i++)
            pixel_write(i,j);
    fclose(fp);
    return 0;
}
void pixel_write(int i, int j){
    static unsigned char color[3];
    color[0] = RD(i,j)&255;
    color[1] = GR(i,j)&255;
    color[2] = BL(i,j)&255;
    fwrite(color, 1, 3, fp);
}

Read more…

趣题:寻找四个共圆的点

5 张矩形的纸片和 6 张圆形的纸片散落在桌面上,如下图所示(其中一张矩形纸片被撕掉了一个角)。考虑所有露在外面的矩形顶点以及纸张边缘处的交点,你能否从中找出四个保证共圆的点?很简单,右下角那个绿色矩形的四个顶点就满足要求,因为矩形的四个顶点显然是共圆的。其实,在这个图里,还有另外三组满足要求的点,你能找到吗?

Read more…

子串复杂度、平衡 01 串与 Sturmian 串

让我们先从两个小问题开始说起。第一个问题是,是否存在某个无限不循环的 01 串,使得对于任意一个正整数 n ,该 01 串中长度为 n 的子串都有且仅有 n + 1 种?

或许这个问题来得有些突然。让我们慢慢解释一下,这个问题是怎么来的。衡量一个 01 串的复杂程度有很多办法,比方说,我们可以去考察它的“子串复杂度”(subword complexity),即子串的种类有多丰富。我们用 pw(n) 来表示,在一个(有可能无限长的)数字串 w 当中,长度为 n 的子串一共有多少种。例如,对于无限 01 串 α = 000000… 来说,不管 n 是多少, pα(n) 永远都等于 1 ;而对于无限 01 串 β = 001001001… 来说,我们有 pβ(1) = 2 ,并且 pβ(2) = pβ(3) = pβ(4) = … = 3 。

注意,虽然 α 和 β 这两个 01 串都是无限的,但是当 n 的值变得很大时, pα(n) 和 pβ(n) 的值始终很小。当然,这一点也不奇怪,因为 α 和 β 是一种特殊的无限 01 串——无限循环 01 串。对于那些无限不循环的 01 串来说,这种事情就不大可能了。在数字串 γ = 01001000100001… 里,长度为 1 的子串只有 {0, 1} 共 2 种,长度为 2 的子串有 {00, 01, 10} 共 3 种,长度为 3 的子串有 {000, 001, 010, 100} 共 4 种,长度为 4 的子串有 {0000, 0001, 0010, 0100, 1000, 1001} 共 6 种……像这样继续计算下去,我们可以得到序列 pγ(1), pγ(2), pγ(3), pγ(4), … 的前面若干项:

2, 3, 4, 6, 9, 12, 16, 20, 25, 30, 36, 42, 49, 56, 64, 72, 81, 90, 100, 110, …

趋势非常明显:随着 n 的增加, pγ(n) 的值也会跟着增加,最终可以增加到任意大。换句话说, pγ(n) 的值没有一个上限。那么,能否找到某个无限不循环的 01 串 w ,使得 pw(n) 的值存在上限呢?不可能!下面我们就来说明,对于任意一个无限不循环的 01 串 w 来说,不管 n 是多少,不等式 pw(n) ≥ n + 1 始终成立。

Read more…