整数分拆中的一个出人意料的结论

把 6 分成一个或多个正整数之和,本质不同的方案只有以下 11 种:

分拆方案 含有多少种不同的数
6 1
5 + 1 2
4 + 2 2
4 + 1 + 1 2
3 + 3 1
3 + 2 + 1 3
3 + 1 + 1 + 1 2
2 + 2 + 2 1
2 + 2 + 1 + 1 2
2 + 1 + 1 + 1 + 1 2
1 + 1 + 1 + 1 + 1 + 1 1

其中,每一行右边的那个数表示,该分拆方案中含有多少种不同的数。把右列的所有数全部加起来,结果是 19 。神奇的是,如果你数一数所有分拆方案中 1 出现的总次数,你会发现结果也是 19 。

这并不是巧合。事实上,对于任意一个正整数来说,各个分拆方案中不同的数的个数之和,一定都等于所有方案中 1 出现的总次数。这是为什么呢?这个结论还有一个比较直接的推广,你能想到吗?

Read more…

实数、超实数和博弈游戏:数学的结构之美

(一)一个博弈游戏

让我们来玩一个游戏。下面有五行石子,白色的石子都是我的,黑色的石子都是你的。我们轮流拿走一个自己的石子,并且规定如果一个石子被拿走了,它后面的所有石子都要被扔掉。谁先没有拿的了,谁就输了。

○●●○●●○●●○
●○○●○●●○●
○○○○
●●●○●●●

Read more…

趣题:顶点数为多少的图有可能和自己互补

若干个顶点以及某些顶点和顶点之间的连线,就构成了一个“图”。如果对某个图进行变换,使得原来任意两个有连线的顶点之间都不再有连线,原来任意两个没有连线的顶点之间现在都有连线了,那么所得到的图就是原来那个图的“补图”。如果一个图和它的补图具有本质上完全相同的结构(这意味着,把其中一个图的顶点以适当的方式与另一个图的顶点建立一一对应的关系,那么对于谁和谁之间有连线、谁和谁之间没有连线这样的问题,两个图的情况是完全一样的),我们就说这个图和它自己是互补的。下图显示了一个顶点数为 5 的图以及它的补图,容易看出,它们的本质结构是相同的。这说明,顶点数为 5 的图有可能和自己互补。

下图显示了一个顶点数为 8 的图,它和它的补图也具有同样的本质结构(你能看出来吗)。这说明,顶点数为 8 的图也有可能和自己互补。

我们今天的问题是:对于那些正整数 n ,存在顶点数为 n 的与自己互补的图?

Read more…

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

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