第三部　一张图

第九章一组表有多难，一张图有多难

李老师听我们讲完正方形上的 $\frac{3}{2}$ ，问了一句：“说成百分数是多少？”

祺乐想了想：“多付一半。单独安排时换 $10%$ 的，就变成 $15%$ 。”

$\frac{3}{2}$ 是一个倍数：答案单上某一步删除实际换地方的机会，比上这一步单独安排时最低要换的机会。祺乐那道题里，每一步都是 $\frac{1}{2}$ 比 $\frac{1}{3}$ 。

可是这个 $\frac{3}{2}$ 是谁的？是祺乐那道题的，还是正方形的？如果四种情况放的是四个一模一样的签盒，答案单只要四栏抄同一个去处，哪一步都不用换。图还是那个正方形，难度却完全不同。所以“难不难”要分成两层说。为了把这两层说清楚，我们把第八章的做法变成了一个游戏。

出题游戏

游戏有两个角色，出题人和安排人。

为什么只看最吃亏的那一种？安排人事先不知道你会做哪一种删除，每一种都得照顾到。一种答案单可能特别照顾某几种删除，却让另一种付出很大代价；那一种删除真的发生了，你碰上的就是那个代价。

我们自己玩过几局，祺乐出题，韵吉安排，瀚林算分。第八章那一局，瀚林在纸上只写了一行：“ $\frac{1}{2} \div \frac{1}{3} = \frac{3}{2}$ ，四种删除都一样。”

游戏里的每一种删除，就是图上的一条边；单独安排时最低要换的机会，就是这条边两端两张表的全变差距离。所以第 3 条规则里的倍数，是答案单上这一步换地方的机会除以这条边的距离。

出题人出定一组表以后，安排人能做到的最低分，叫这组表的最优因子，记作 $ρ$ ，这是希腊字母，读作“柔”。祺乐那道题的最优因子是 $\frac{3}{2}$ 。

祺乐又出了一局：四个签盒一模一样。瀚林算分算到第一步就停了笔，这一步的距离是零，没法除。

这个麻烦是真的，我们在上面卡了不少时间。只要某条边两端的表完全一样，距离就是零，倍数的分母也就是零。

祺乐说，距离是零的边，干脆不算。韵吉在白板上画了两个一样的签盒，中间连一条线：“这两个签盒一模一样，你让它们抽出不同的去处？”祺乐没再争，在那条线旁边写了“ $= 0$ ”。

这就像第五章删掉“最喜欢蓝色”：删前删后的签盒相同，共用一枚硬币，就一次也不用换。两张表一样时，我们更希望回答完全不变，把这样的边直接丢掉不行。

于是游戏多了第 5 条规则：单独安排时一次也不用换的删除，答案单上也必须一次都不换，不参加除法。写成数学的说法，就是距离为零的边不放进比值里，另外单独要求它两端的回答永远相同。

这个要求并不太严，总能做到。把由距离为零的边连在一起的顶点看成一组，组里的表都一样，就让整组共用一次抽签的结果。不同的组之间再另行安排。

回到四个签盒一模一样的那一局。四种删除都归第 5 条规则管，安排人让答案单四栏抄同一个去处就行，没有一个倍数可算。这一局安排人完胜，记 $0$ 分：所有边的距离都是零时，这组表的最优因子记作 $0$ 。

一局只看一组表。整场比赛里，图固定不变，出题人可以一局一局地换表，回答的种类也可以随便多，不再限于四个去处。出题人在这张图上能逼出的最高分，叫这张图的耦合常数，记作 $c (G)$ ， $G$ 代表这张图。

还要一个记号：把 $n$ 个顶点依次连起来、最后一个再连回第一个，围成的圈记作 $C_{n}$ 。三角形是 $C_{3}$ ，我们的正方形就是 $C_{4}$ 。

我们后来证明了 $c (C_{4}) = \frac{3}{2}$ 。这句话的意思是两件事同时成立：

第二件，第八章已经做到了。第一件要到第十一章才证明。

再回到李老师的问题。 $c (C_{4}) = \frac{3}{2}$ 给的是一个保证：在正方形上，不管签盒怎么放，单独安排时只要换 $10%$ 的那一步删除，放进最好的答案单里也不会超过 $15%$ 。实际可能更低，这只是一个上限。

到这里，我们的研究问题可以写成两问。

韵吉把这两个问题抄进了本子。

我们把已经知道的数画在一条线上，叫它记分牌，后面还会把新求出的数陆续填上去。线的右端标着 $2$ ，它从哪里来，后面几部会讲到。