第三部　一张图

第八章四张表，互相为难

祺乐说：“我来给答案单出一道难题。”

规矩是这样的：四种情况，每种都有一个去处绝对不去，而且四种情况不去的各不相同；其余三个去处，机会一样多。我们沿着正方形，把四种情况依次叫作顶点 $1$ 、 $2$ 、 $3$ 、 $4$ 。表里的甲、乙、丙、丁，还是电影院、公园、图书馆、游乐场：

顶点	情况	甲	乙	丙	丁
$1$	只剩怕吵	$0$	$\frac{1}{3}$	$\frac{1}{3}$	$\frac{1}{3}$
$2$	两条都删	$\frac{1}{3}$	$0$	$\frac{1}{3}$	$\frac{1}{3}$
$3$	只剩电影	$\frac{1}{3}$	$\frac{1}{3}$	$0$	$\frac{1}{3}$
$4$	两条都在	$\frac{1}{3}$	$\frac{1}{3}$	$\frac{1}{3}$	$0$

顺着 $1$ 、 $2$ 、 $3$ 、 $4$ 再回到 $1$ ，每走一步都只差一条记录，所以这四种情况确实沿正方形排成一圈，四条边都是一次删除。

每张表只排除一种回答，其余三种平分。我们把它叫作逐一缺失的一组表。

这四个签盒，只有一个勉强说得通：两条都在时，助手记得你怕吵，不去游乐场。另外三个就说不通了：只剩怕吵时，凭什么一次也不去电影院，倒有三分之一去吵闹的游乐场？两条都删以后，又凭什么偏不去公园？真实的助手大概不会这样回答。这是祺乐故意出的难题。出题的人可以不管记录说了什么，因为我们要找的是最坏的情况。

所以下面的道理只看顶点编号和甲乙丙丁，用不着记录的意思。

图 6：正方形上的逐一缺失：每个顶点各有一种回答不能出现。 — 图 6正方形上的逐一缺失：每个顶点各有一种回答不能出现。

先看一条边，比如顶点 $1$ 和 $2$ 。两张表只在甲和乙上不同：甲从 $0$ 变成 $\frac{1}{3}$ ，乙从 $\frac{1}{3}$ 变成 $0$ 。差的绝对值加起来是 $\frac{2}{3}$ ，除以 $2$ ，全变差距离是 $\frac{1}{3}$ 。四条边都一样。所以，如果每条边单独处理，变化的机会最低都能降到 $\frac{1}{3}$ 。

每张签至少有两条边不同

祺乐让韵吉和瀚林先试试：画四个格子，第一格不许写甲，第二格不许写乙，第三格不许写丙，第四格不许写丁，看能不能四格写成同一个字。瀚林试乙，第二格不行；试丙，第三格不行。韵吉没动笔：“哪个都不行吧？”

确实不行。四栏写成同一个回答，不管选哪一个，总有一栏不许写它。所以每张签上，四个顶点的回答不全相同。沿着正方形转一圈，比较每一对相邻的顶点，至少会碰到几条“两端不同”的边？

至少两条。假如只有一条边两端不同，其余三条边两端都相同，那么从这条边的一端出发，沿另外三条边绕回来，回答一路没变，走到这条边的另一端时还是同一个回答，这条边的两端就也相同了。这和“两端不同”矛盾。一个圈就像一条首尾相接的项链，从一种颜色换成另一种，要回到起点就必须再换回来，换色的地方总是成对出现。

每一张签都至少有两条边不同。那么不管各种签的机会怎样分配，平均下来，每张签不同的边数也至少是 $2$ 。

下面这一步后面会用到很多次，我们慢一点看。这里的平均要按机会算：机会大的签算得重一些，每种签的边数先乘上它的机会，再加起来。“平均每张签有几条边不同”，正好等于“四条边各自不同的机会”加起来。用一个随便编的例子来看。假设只有三种签：

签	机会	$1$ — $2$	$2$ — $3$	$3$ — $4$	$4$ — $1$	边数
一	$\frac{1}{2}$	$∙$	$∙$			$2$
二	$\frac{1}{4}$	$∙$	$∙$	$∙$	$∙$	$4$
三	$\frac{1}{4}$			$∙$	$∙$	$2$
合计		$\frac{3}{4}$	$\frac{3}{4}$	$\frac{1}{2}$	$\frac{1}{2}$

表里的圆点表示这张签上这条边两端不同，最后一列是这张签上不同的边数，最后一行是每条边不同的机会。按行算，平均每张签不同的边数是 $\frac{1}{2} \times 2 + \frac{1}{4} \times 4 + \frac{1}{4} \times 2 = \frac{5}{2}$ 。按列算，四条边不同的机会加起来是 $\frac{3}{4} + \frac{3}{4} + \frac{1}{2} + \frac{1}{2} = \frac{5}{2}$ 。两个数一样，因为它们数的是表里同一批“不同”，只是一个先按行、一个先按列。

图 7：把三种签的表画成横带：每张签一条，带高等于它的机会，涂色的格子是两端不同的边；涂色面积按行加、按列加都是 5/2。 — 图 7把三种签的表画成横带：每张签一条，带高等于它的机会，涂色的格子是两端不同的边；涂色面积按行加、按列加都是 $\frac{5}{2}$ 。

所以，四条边不同的机会加起来至少是 $2$ 。

如果四条边都达到了单独最好的 $\frac{1}{3}$ ，加起来只有 $\frac{4}{3}$ ，比 $2$ 小，这不可能。所以四条边不能同时达到各自的最好成绩。

祺乐说：“我这道题出得还行。”

再推紧一点：四个数加起来至少是 $2$ ，其中最大的那个至少是 $\frac{1}{2}$ ，因为四个数要是都比 $\frac{1}{2}$ 小，加起来就不到 $2$ 。也就是说，不管怎样安排，至少有一条边不同的机会不少于 $\frac{1}{2}$ 。和它单独的最好成绩 $\frac{1}{3}$ 相比，至少放大到了 $\frac{1}{2} \div \frac{1}{3} = \frac{3}{2}$ 倍。

一种刚好做到的抽法

这只说明不能比 $\frac{3}{2}$ 更好。会不会还要更坏？要知道最好的安排到底是多少，还得交出一种真能做到 $\frac{3}{2}$ 的抽法。

我们这样抽：先从四个顶点里等机会挑一个“特殊顶点”，用字母 $J$ 记下它。和 $J$ 编号对应的那个回答（ $J = 1$ 对应甲， $J = 2$ 对应乙，依此类推），写在其余三个顶点上； $J$ 自己不能写这个回答，就从另外三种里等机会挑一个写上。

比如 $J = 2$ ：顶点 $1$ 、 $3$ 、 $4$ 都写乙，顶点 $2$ 从甲、丙、丁里挑一个。整张签只有一个顶点和别人不同，正方形上恰好是和它相连的那两条边两端不同。

放回周末去看，顶点 $2$ 就是“两条都删”。这张答案单上，另外三种情况都写公园；“两条都删”不许去公园，就从电影院、图书馆、游乐场里挑一个。只有走进“两条都删”的那两步删除会换地方。

图 8：特殊顶点是 2 的时候：其余三个顶点都写乙，只有连着顶点 2 的两条边两端不同。 — 图 8特殊顶点是 $2$ 的时候：其余三个顶点都写乙，只有连着顶点 $2$ 的两条边两端不同。

每一栏的边际分布对不对？看顶点 $1$ 。它永远不会写甲： $J = 1$ 时它自己从乙、丙、丁里挑； $J$ 是别的顶点时，它写的是 $J$ 对应的回答，也不是甲。它写乙有两种可能： $J = 2$ ，机会 $\frac{1}{4}$ ；或者 $J = 1$ 而它恰好挑中了乙，机会 $\frac{1}{4} \times \frac{1}{3} = \frac{1}{12}$ 。合起来是 $\frac{1}{4} + \frac{1}{12} = \frac{1}{3}$ 。写丙、写丁也一样。所以顶点 $1$ 这一栏正好是它那张表。其余顶点同理。

每条边呢？只有当 $J$ 是这条边的两个端点之一时，两端才不同，机会是 $\frac{2}{4} = \frac{1}{2}$ 。四条边都是 $\frac{1}{2}$ ，刚好碰到前面证明的下限。

瀚林想自己数一遍。我们把这种抽法的十二种签抄在十二张纸条上，每种的机会都是 $\frac{1}{12}$ ，然后一条边一条边地数两端不同的纸条。四条边，每条都数出六张，六张占十二张的一半，正好是 $\frac{1}{2}$ 。书末附录一也列出了这十二种签，你可以亲手数一数。

所以，对这组表来说，最好的共同安排使每条边最多放大到 $\frac{3}{2}$ 倍，而且不能更好了。

圈带来的麻烦

每条边单独都能做到最好，合在一起却做不到，我们整个研究要对付的就是这种现象。

毛病出在这些边连成了一个圈上。树上没有这个麻烦，第十章会讲到。圈却让各条边的“最好安排”互相牵制，一条边做到了最好，别的边就可能做不到。

回到周末。对祺乐出的这道题，不管答案单怎么写，四种删除里总有一种，至少有 $\frac{1}{2}$ 的机会换地方，而它单独安排时只要 $\frac{1}{3}$ 。四个数加起来至少是 $2$ ，最大的又不超过 $\frac{1}{2}$ ，只能四个都是 $\frac{1}{2}$ 。所以最好的答案单上，四种删除换地方的机会都是 $\frac{1}{2}$ 。