奇偶性 — 不试一次,也能断定「做不到」
这一章讲三件事: 只分两组、只看单双,凭什么能传信息、能查错; 为什么它能在一次试验都不做的前提下断定「这件事做不到」; 以及这种断定有一条硬边界——它只证得了「不能」。
它在全书链条里的位置: 第 06 章把无穷多个数分成 7 组。 这一章把组数压到最少的 2 组,而威力反而最大。 这也是原书余数那一章的收尾。需要的基础: 知道什么是奇数偶数就够了。
1. 先看现象:蒙着眼睛的魔术师
台上一个魔术师、一个徒弟,台下三位观众。魔术师全程蒙着眼睛1。
① 桌上随机摆 7 枚黑白棋 魔术师看不见
② 徒弟看过之后,在右边再添 1 枚 → 现在 8 枚,魔术师仍然看不见
③ 观众可以翻转其中 1 枚,也可以一枚都不动 —— 全程不说话
④ 魔术师摘下眼罩,看一眼这 8 枚,当场说出「观众翻过」或者「没翻过」
图说:全章的主走查就是这一局。
徒弟和魔术师从头到尾没说过一个字,信息全在第 ② 步那一枚棋子上。
魔术师怎么知道的? 他没看过原来那 7 枚,所以不可能是「记住了再对比」。 徒弟只放了一枚棋子,而且是在观众动手之前放的2—— 这一枚棋子,就是全部的通信量。
下面这一局的具体摆法是我们为演示编的(原书只说「随机排列」,没有给具体的棋子):
第 ① 步,桌上 7 枚: ○ ● ○ ● ● ○ ○ 黑棋 3 枚(奇数)
2. 徒弟那一枚棋子,传的是一个「单双」
这一节回答:一枚棋子能传什么。
徒弟的做法只有一条规则:数一数黑棋有几枚3:
- 黑棋是奇数枚 → 添一枚黑棋;
- 黑棋是偶数枚 → 添一枚白棋。
不管原来是几枚,添完之后,黑棋一定是偶数枚4。
第 ② 步:原来黑棋 3 枚(奇数)→ 徒弟添一枚黑棋
○ ● ○ ● ● ○ ○ | ● 现在 8 枚,黑棋 4 枚(偶数)
↑ 徒弟添的
这是主走查的第一、二步。
注意徒弟做的事有多小:他没有传「原来是什么摆法」,只传了一件事—— 「我已经把黑棋的个数凑成偶数了」。 魔术师事先知道的也只有这一句约定。
3. 观众一动手,单双一定翻面
这一节回答:凭这一句约定,怎么就能识破观众。
观众只有三种可能的行为,而三种全都被这一句约定盖住了5:
| 观众干了什么 | 黑棋数怎么变 | 变成 |
|---|---|---|
| 翻转一枚白棋(白变黑) | 4 → 5,多一枚 | 奇数 |
| 翻转一枚黑棋(黑变白) | 4 → 3,少一枚 | 奇数 |
| 什么都不动 | 4 不变 | 偶数 |
关键在这里:翻转任何一枚棋子,黑棋数都会变化 1,而「变化 1」必定改变单双。 多一枚也好、少一枚也好,偶数一定变成奇数——方向不重要,只有奇偶重要。
第 ③ 步:观众翻了一枚白棋
○ ● ○ ● ● ● ○ | ● 黑棋 5 枚(奇数)
↑ 被翻的那一枚
第 ④ 步:魔术师摘下眼罩,数出黑棋 5 枚 —— 奇数 —— 于是断定「观众翻过」
这是主走查的第三、四步,走完了。 魔术师的判断规则同样只有一句: 黑棋是奇数就说「翻过」,是偶数就说「没翻过」6。
这一局里没有任何猜测。 徒弟约定的是「偶 数」,观众只要动手就会变成奇数, 所以魔术师的判断是必然正确的,不是概率上正确。 (原书补了一句:约定成「凑成奇数」也一样,只要两人事先说好7。)
4. 这不是魔术,是通信里的奇偶校验
这一节回答:这一局在真实系统里对应什么。
把白棋看成 0、黑棋看成 1,这一局就是计算机通信里的查错办法8:
| 魔术里的角色 | 通信里的角色 |
|---|---|
| 徒弟 | 发送方 |
| 那 7 枚棋子 | 要发的数据 |
| 徒弟添的那一枚 | 校验位 |
| 中途翻棋子的观众 | 线路上的干扰 |
| 魔术师 | 接收方 |
中途把 0 变成 1、把 1 变成 0 的那些干扰,通信里管它叫噪声9; 而徒弟添的那一枚,正式名字叫奇偶校验位10。 接收方收到之后数一数单双,就知道路上有没有出错—— 至于约定成偶数还是奇数,那是收发双方事先商量好的11。
代价小得惊人:7 位数据只多发 1 位,就换来了「能发现出错」的能力。
5. 它能查出什么,查不出什么
这一节回答:这么便宜的办法,是不是有什么没说的代价。
有,而且很明确。 先看它做到了什么: 7 枚棋子一共有 2 的 7 次方 = 128 种摆法,其中黑棋为偶数的正好 64 种, 黑棋为奇数的也是 64 种12。
徒弟添的那一枚,作用就是标明「原来这 7 枚属于哪一组」13—— 一枚棋子只能传一位信息,而它正好够回答「在这一半还是那一半」。
但代价也在这里:它只知道单双变没变,不知道具体哪一位变了。 而且——如果观众同时翻两枚棋子,单双不变,魔术师就被骗过去了。 (这一条是我们从上面那张表直接推出来的:两次变化各改一次单双,一来一回抵消了。 原书没有明说这一点。)
6. 换个场子:铺不满的房间——而这套判定只能证「不能」
这一节另起一处走查,并且交代这套办法唯一的硬边界。
题目:一个不规则形状的房间,能不能用整张草席正好铺满(不许用半张)?14
第一次尝试是数面积。 以「半张草席」为单位量一量,房间正好是 62 个半张—— 62 是偶数,所以从个数上看不出问题15。这条路走不通。
第二次尝试换了个分类:把房间像国际象棋盘那样涂成黑白相间16:
┌── ─┬───┬───┬───┐
│ ● │ ○ │ ● │ ○ │ 数一数:
├───┼───┼───┼───┤ 黑色的半张 …… 30 块
│ ○ │ ● │ ○ │ ● │ 白色的半张 …… 32 块
├───┼───┼───┼───┘
│ ● │ ○ │ ● │ 而一整张草席横竖都占相邻两格,
└───┴───┴───┘ 所以必定盖住一黑一白。
图说:每铺一张草席,黑白各消耗一块。要铺满,黑白必须一样多。
30 ≠ 32,所以铺不满 —— 一种铺法都不用试。
黑 30、白 32,差了 217。一整张草席不管横放竖放,都盖住一黑一白, 所以要铺满,黑白块数必须相等。结论:铺不满18 。
这一处的收益是:铺法有很多种,要证明「铺不满」本来得把所有铺法列一遍; 而涂个色数一数,一次试验都不用做19。
同一招还能用在别的地方,这里只举一例、不展开: 原书那道「寻找恋人」的题里,八个村子按「走奇数次能到」和「走偶数次能到」分成两组, 从起点走 12 次(偶数次)必定落在偶数村那一组,而目标村不在那一组—— 所以答案是 0,一条路线都不用列20。
但这里有一条必须写进标题的边界:这套判定只能证「不能」。 原书说得很直白:如果黑白块数相加不为 0,就铺不满; 可假如算出来正好为 0,也并不能保证一定铺得满—— 因为「逆命题不一定为真」21。
第 04 章那条判断在这里落地了: 「铺得满 ⇒ 黑白一样多」成立, 倒过来说不成立。 这类判定是一把筛子,能筛掉不可能的,筛不出可行的。
最后一句是原书对这套办法的总结:要做有效的奇偶校验, 必须找到「合适的分类方法」22——恋人那题分的是奇偶村,草席这题涂的是黑白格。 分类找不对,这招就使 不出来;而找分类靠的是灵感,书里也这么承认23。
7. 一笔画:先把地图简化成点和线
这一节另起第二处走查,它是这一章的压轴。
题目(哥尼斯堡七桥): 一条河把小城分成四块陆地,中间架了 7 座桥。 能不能每座桥只走一次,把 7 座桥全走遍?(可以重复经过同一块陆地, 起点随便挑,也不用回到起点)24
先试走一遍: 从 A 出发过桥 a 到 B、过桥 b 回 A、过桥 c 到 C、过桥 d 回 B、 过桥 e 到 D、过桥 f 回 B——卡住了,和 B 相连的桥全走过了,桥 g 走不到25。
多试几次都走不通。但「试了很多次都不行」不等于「不可能」—— 说不定只是你没找到那条路26。要下结论,必须证明。
第一步是扔掉地图。 陆地画成一个圆圈,桥画成一条线, 别的信息(陆地多大、桥多长)全部不 要27:
(A)────────┐
│ │ │
a b c
│ │ │
(B)───d────(C)
│ │ │
e f g
│ │ │
(D)────────┘
图说:圆圈是陆地,线是桥。
左边那两对竖线不是画重了:A 和 B 之间本来就架着两座桥(a 和 b),
B 和 D 之间也是两座(e 和 f)。原来的地图变成了 4 个圆圈、7 条线 ——
剩下的全是干扰。
这种只画「谁和谁连着」的图形,原书称为图28。 从这里往下,「陆地」和「桥」这两个词就不再出现了——只剩这张图。
图上那两样东西也各有名字:圆圈叫顶点,连线叫边。 这两个名字值得记住——出了这本书,别人讲同类问题时用的都是它们。
扔掉的东西越多,越容易看清剩下的。 这一步和第 06 章「只看余数不看数」是同一个动作。
8. 判据:奇点最多两个 —— 欧拉的答案
这一节把上一节的图变成一句判据,并走完主走查之外的最后几个数。
先给一个数下定义:一个顶点连着几条边,这个数就叫它的度数29。 照上一节那张图数一个:顶点 C 连着 c、d、g 三条线,所以 C 的度数是 3。
再按度数是单是双,把顶点分成两类:度数是偶数的叫偶点,是奇数的叫奇点30。 C 的度数 3 是奇数,所以 C 是奇点。
接下来是整个论证的核心,只有三句话31:
| 什么时候 | 度数怎么变 |
|---|---|
| 从起点出发 | 起点的度数减 1 |
| 中途经过某个顶点 | 走进来一条边、走出去一条边,减 2 |
| 到达终点 | 终点的度数减 1 |
中间那一条是关键:每经过一次减 2,而减 2 不改变奇偶。 所以一个顶点无论被经过多少次,它是奇点还是偶点都不会变32。
于是可以倒着推: 假如真的一笔画成了,所有边都走过,所有顶点的度数最后都减到 0 (偶数)。中途经过的点减的都是偶数,所以它们本来就是偶点; 只有起点和终点各多减了 1——它们本来是奇点33。
判据:能一笔画成 ⇒ 要么所有顶点都是偶点,要么正好有 2 个奇点
回到七桥,数一数四个顶点的度数34:
顶点 A:连着 a、b、c 三条边 …… 度数 3(奇点)
顶点 B:连着 a、b、d、e、f 五条边 …… 度数 5(奇点)
顶点 C:连着 c、d、g 三条边 …… 度数 3(奇点)
顶点 D:连着 e、f、g 三条边 …… 度数 3(奇点)
四个顶点全是奇点,而判据只允许 0 个或 2 个。
→ 七桥走不完。一条路线都不用试。
这就证完了35。原书对这件事的评价是:欧拉这条论断的重点在于—— 不反复试验也能证明不能一笔画成36。
这条判据是欧拉在解这道七桥题时给出的,而图论就是从这儿起头的37。 (补充,不在书里: 欧拉 1735 年 8 月把这个解法交给圣彼得堡科学院, 1736 年完成的这份不可能性证明被视为图论的起点,论文 1741 年才正式发表38。)
最后一件事,原书用脚注交代、我们必须转述: 这条判据的逆命题也成立——所有顶点都是偶点、或者正好两个奇点, 就一定能一笔画成;只是原书省略了这个方向的证明39。
注意这和第 6 节的草席不一样: 草席那套判定只能证「不能」, 而一笔画这条判据两个方向都成立。 「逆命题不一定为真」的意思是「不一定」,不是「一定不」。
9. 作者的判断、我们的判断,以及这一章的边界
| 说法 | 书里给了什么 |
|---|---|
| 魔术师能识破观众 | 给了完整机制:三种行为逐一验过,没有漏 |
| 一枚棋子把 128 种摆法分成两组 | 给了数(64 + 64),这是这一章唯一一处算给你看的账 |
| 涂色能证明铺不满 | 给了完整走查(30 与 32),并且明说逆命题不成立 |
| 七桥走不完 | 给了完整证明(度数减 1 / 减 2 / 减 1 那三句) |
| 「找到合适的分类方法」靠灵感 | 是作者的说法,原文用的词就是「灵感」,没有给方法 |
| 同时翻两枚就骗过去了 | 书里没有明说,是我们从三种情况的表里推的 |
判断(我们的,不是书里的):这一章教的是一种「证不可能」的能力, 而这种能力在工程里被严重低估。 程序员的默认动作是「试一试」——试不通就改一改再试。 而这一章的两道题告诉你:有些时候,先花五分钟找一个合适的分类, 就能直接排除掉整片搜索空间。 如果错,会错在: 这条本事的门槛很高——找到那个「合适的分类」几乎全靠灵感, 书里自己也这么说。 找不到的时候,这一章什么也给不了你。 判据是:你手上那个问题,能不能找出一个「每走一步就必定翻面」的量。
这一章的边界:
- 奇偶校验只能发现「有奇数个位出错」,同时错两位就查不出来—— 原书没有讨论这一点,也没有提能纠错的更强办法;
- 一笔画那条判据的逆方向,原书省略了证明;
- 「合适的分类 」怎么找,书里给不出方法,只给了「需要灵感」四个字;
- 图论到此为止——原书没有再往下讲路径、连通、最短路这些后续内容;
- 七桥的历史背景很薄:原书只在脚注里提了哥尼斯堡是康德的故乡、现在叫加里宁格勒。
10. 可带走的
- 只分两组、只看单双,是分组能压到的极限——而它反而最有力;
- 翻转任何一枚棋子都会让黑棋数变化 1,而变化 1 必定改变单双——方向不重要;
- 一位信息正好够回答「在这一半还是那一半」:128 种摆法被切成 64 + 64;
- 通信里的名字:那一位叫奇偶校验位,路上的干扰叫噪声;
- 它能发现「出过错」,但不知道错在哪一位;同时错两位就查不出来;
- 奇偶性能证明「做不到」:黑 30 白 32,一种铺法都不用试就知道铺不满;
- 但这类判定只证得了「不能」——反过来数目相等也不保证铺得满(逆命题不一定为真);
- 一笔画的判据:奇点要么 0 个、要么 2 个;七桥四个顶点全是奇点,所以走不完;
- 这条判据是欧拉解七桥时给出的,图论就是从这儿起头的;
- 通用动作:扔掉所有不影响结论的信息——地图扔成点和线,数值扔成单双。
11. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 黑白棋魔术的四步 | 第3章 余数 | text/08-ch03.txt:265(搜「桌上随机排列着 7 枚黑白棋的棋子」) · :283(搜「魔术师摘下眼罩」) |
| 徒弟的规则与三种情况 | 第3章 余数 | text/08-ch03.txt:300(搜「如果黑棋数是奇数」) · :301(搜「黑棋必为偶数个」) · :304(搜「观众翻转白棋」) |
| 奇偶校验、噪声、校验位 | 第3章 余数 | text/08-ch03.txt:314(搜「白棋为 2 进制的 0」) · :316(搜「的噪声」) · :318(搜「奇偶校验位」) |
| 128 种摆法分成两组 | 第3章 余数 | text/08-ch03.txt:324(搜「7 枚棋子的排列法总共有」) · :326(搜「起到了标识目前 7 枚棋子的摆法属于哪组的作用」) |
| 寻找恋人 | 第3章 余数 | text/08-ch03.txt:374(搜「答案：概率为 0」) · :387(搜「我们并不着眼于路线，而是关注目的地」) |
| 铺草席 | 第3章 余数 | text/08-ch03.txt:432(搜「可是 62 是偶数」) · :444(搜「黑色的」) · :450(搜「不能正好铺满房间」) · :461(搜「逆命题不一定」) |
| 简化成图、顶点、边 | 第3章 余数 | text/08-ch03.txt:534(搜「称作「图」」) · :535(搜「我们称其为「顶点」」) · :536(搜「我们称其为「边」」) |
| 度数、奇点偶点、判据 | 第3章 余数 | text/08-ch03.txt:557( 搜「称作该顶点的度数」) · :564(搜「度数为偶数的顶点称为」) · :612(搜「可以一笔画成」) · :617(搜「4 个顶点都是奇点」) |
| 欧拉与图论 | 第3章 余数 | text/08-ch03.txt:537(搜「数学家莱昂哈德」) · :538(搜「这就是图论的开山鼻祖」) · :637(搜「不反复试验也能证明不能一笔画成」) |