第十一章在圈上拿掉一条边

在一个圈上任意拿掉一条边，剩下的就是一条经过所有顶点的路，这是一棵树。按上一章的办法，留下来的每条边都能做到最大耦合。

问题是被拿掉的那条边。它不参与构造，可它仍然是我们要照顾的一条边。

放到两条记录的正方形上，拿掉一条边是这样一件事：助手在写答案单之前先定下来，这一回不专门照顾哪一种删除。被放下的那一种，只能靠其余三步连带着照顾。

被拿掉的边会怎样

被拿掉的那条边，两个端点之间仍然有剩下的那条路连着。如果路上每一条边两端都相同，那么从一个端点一路走到另一个端点，回答一直没变，被拿掉的边两端也就相同。所以，被拿掉的边两端不同，一定是因为路上至少有一条边两端不同。

几件事里至少有一件发生的机会，不会超过它们各自机会的和。比如明天下雨的机会是 $\frac{3}{10}$，刮大风的机会是 $\frac{2}{10}$，那么“下雨或者刮大风”的机会最多是 $\frac{5}{10}$；如果两件事可能同时发生，实际还会更小。这个简单的道理叫并集上界。

用它就得到：被拿掉的边两端不同的机会，不超过路上各条边不同的机会之和。

下面要用到式子。圈上的一条边记作 $e$，它两端两张表的全变差距离记作 $d_e$，字母下面的小 $e$ 表示“这一条边”。把圈上所有边的距离加起来，记作 $D$。路上的边都做到了最大耦合，它们不同的机会就是各自的距离。所以：

• 一条边留下时，它不同的机会恰好是 $d_e$；
• 一条边被拿掉时，它不同的机会不超过 $D-d_e$，也就是其他所有边的距离之和。

轮流拿掉

总拿掉同一条边，坏处就全落在这一条边上。所以在正式抽签之前，我们先随机决定拿掉哪一条。

这样一来，抽签分成了两步：第一步抽“拿掉哪条边”，第二步沿剩下的路抽签。算一条边两端不同的机会，就像初中画树状图那样：先分出“它留下”和“它被拿掉”两个枝，每个枝上把两步的机会相乘，最后把两个枝加起来。

先看各条边距离都一样的情形。设圈上有 $n$ 条边，每条的距离都是 $d$，那么 $D=nd$。每条边被拿掉的机会都是 $\frac{1}{n}$。对任意一条边：

• “留下”这个枝：机会 $1-\frac{1}{n}$，这时它不同的机会是 $d$；
• “被拿掉”这个枝：机会 $\frac{1}{n}$，这时它不同的机会不超过 $D-d$，也就是 $(n-1)d$。

合起来，它不同的机会不超过 $$(1-\frac{1}{n})d+\frac{1}{n}(n-1)d=(2-\frac{2}{n})d$$ 放大的倍数不超过 $2-\frac{2}{n}$。三角形是 $\frac{4}{3}$，正方形是 $\frac{3}{2}$，正好对上第八章的那个数。

距离不一样的时候

可是各条边的距离往往不一样。这时候让每条边被拿掉的机会都一样，就不行了。

举个例子，还是两条记录的正方形。这回只说距离，不写签盒，数是假设的。两条都在时删掉“怕吵”，几乎不影响回答，反正周六要去看电影，单独安排只有 $\frac{1}{10}$ 的机会换地方。另外三种删除都要紧一些，距离各是 $\frac{3}{10}$。四条边加起来 $D=1$。

如果每条边都以 $\frac{1}{4}$ 的机会被拿掉，那条距离只有 $\frac{1}{10}$ 的小边，不同的机会最多会达到 $$\frac{3}{4}\times \frac{1}{10}+\frac{1}{4}\times (1-\frac{1}{10})=\frac{3}{40}+\frac{9}{40}=\frac{3}{10}$$ 是它单独最好成绩的 $3$ 倍。被拿掉时它承受的 $\frac{9}{10}$，除以一个很小的分母，倍数就大了。

所以我们要让各条边的倍数一样大，这就要让距离小的边少被拿掉一些。

先在例子上算

还是这个正方形。设小边被拿掉的机会是 $x$，三条大边被拿掉的机会都是 $y$，那么 $x+3y=1$。

小边留下时，不同的机会是 $\frac{1}{10}$；被拿掉时，最多是其余三条边的距离之和 $\frac{9}{10}$。按两个枝相加，它不同的机会最多是 $$(1-x)\cdot \frac{1}{10}+x\cdot \frac{9}{10}=\frac{1}{10}+\frac{8}{10}x$$ 除以它自己的距离 $\frac{1}{10}$，倍数最多是 $1+8x$。

同样，一条大边留下时不同的机会是 $\frac{3}{10}$，被拿掉时最多是其余三条之和 $\frac{7}{10}$，所以最多是 $\frac{3}{10}+\frac{4}{10}y$，倍数最多是 $1+\frac{4}{3}y$。

最吃亏的边决定了整体的倍数，所以最好让两种边“额外多出来的倍数”一样大：$8x=\frac{4}{3}y$，也就是 $y=6x$。代进 $x+3y=1$，得到 $19x=1$，所以 $$x=\frac{1}{19},y=\frac{6}{19}$$

祺乐解到这里停了一下：“十九分之一？”

我们都没想到会冒出一个 $19$。瀚林把 $\frac{1}{19}$ 和 $\frac{6}{19}$ 抄下来，四条边一条一条代进去：小边是 $1+8\times \frac{1}{19}$，三条大边都是 $1+\frac{4}{3}\times \frac{6}{19}$。白板上四行算式，最后都是 $\frac{27}{19}$。

那种不要紧的删除，只有 $\frac{1}{19}$ 的机会被放下；三种要紧的删除，各有 $\frac{6}{19}$ 的机会被放下。这样每种删除最多多付到 $\frac{27}{19}$ 倍，大约 $1.42$ 倍。比均匀拿掉时小边的 $3$ 倍好得多，也没超过正方形的 $\frac{3}{2}$。

推广到任意的圈

祺乐把这个算法推广到了任意的圈。从这里起去掉名字，只看边和距离。设边 $e$ 的距离是 $d_e$，被拿掉的机会是 $p_e$。和上面一样，它不同的机会最多是 $$(1-p_e)d_e+p_e(D-d_e)=d_e+p_e(D-2d_e)$$ 除以 $d_e$，倍数最多是 $1+p_e\cdot \frac{D-2d_e}{d_e}$。要让每条边额外多出来的倍数都一样大，$p_e$ 就要和 $\frac{d_e}{D-2d_e}$ 成正比。把所有边的 $\frac{d_e}{D-2d_e}$ 加起来，记作 $$S=\sum _e\frac{d_e}{D-2d_e}$$ （$\sum$ 读作“求和”，意思是对每条边都算一遍再加起来。）那么每条边被拿掉的机会就是 $\frac{1}{S}\cdot \frac{d_e}{D-2d_e}$，所有边的倍数都不超过同一个数 $1+\frac{1}{S}$。这个选法，我们叫它祺乐的平衡式。后来查文献才知道，前人在一种特殊情形里已经写出过同样形式的式子，第二十四章会讲到。

用刚才的例子核对：小边的 $\frac{d_e}{D-2d_e}=\frac{1/10}{8/10}=\frac{1}{8}$，大边各是 $\frac{3/10}{4/10}=\frac{3}{4}$，$S=\frac{1}{8}+\frac{9}{4}=\frac{19}{8}$。小边被拿掉的机会是 $\frac{8}{19}\times \frac{1}{8}=\frac{1}{19}$，大边是 $\frac{8}{19}\times \frac{3}{4}=\frac{6}{19}$，倍数是 $1+\frac{8}{19}=\frac{27}{19}$。和解方程得到的完全一样。

祺乐推出这个平衡式以后，也请 AI 核算过。AI 说“对”以后，我们仍然像上面这样把例子一条边一条边地代进去，确认每条边的倍数真的都一样。

两种要先排除的情况

祺乐把式子写上白板，韵吉只看了一眼，就指着分母问：“那 $D$ 减 $2d$ 等于零呢？”

祺乐愣了一下。两个人一起找，很快凑出一个例子：正方形四条边的距离是 $\frac{1}{2}$、$\frac{1}{2}$、$0$、$0$。这时 $D=1$，前两条边的 $D-2d_e$ 都是零，平衡式根本没法算。

式子里有 $D-2d_e$ 做分母，所以有两种情况要先单独处理。

第一种，$D=0$，所有边的距离都是零，各个顶点的表全一样。那就抽一次，把同一个回答抄给所有顶点。

第二种，某条边的距离恰好是 $D$ 的一半。这里要用到全变差距离的一个性质：从一张表改到另一张表，绕道经过别的表，需要挪动的机会不会比直接改更少。这叫三角不等式。所以任何一条边的距离，都不超过圈上其余各边距离之和，也就是 $d_e\le D-d_e$，即 $d_e\le \frac{D}{2}$。如果某条边正好等于 $\frac{D}{2}$，就固定拿掉它：它两端不同的机会不超过 $D-d_e=d_e$，等于它自己的距离。于是所有边都做到了最大耦合。刚才那个例子，就固定拿掉一条 $\frac{1}{2}$ 的边。

除了这两种情况，所有正的距离都严格小于 $\frac{D}{2}$，分母都是正数，平衡式可以放心用。距离为零的边，我们从不拿掉它，让它一直留在路上，两端永远相同。

平衡以后最多是多少

圈上距离为正的边如果有 $m$ 条，平衡以后的倍数 $1+\frac{1}{S}$ 一定不超过 $2-\frac{2}{m}$，所以也不超过 $2-\frac{2}{n}$。直观上说，各条边距离都相等是最坏的情形，这时正好是 $2-\frac{2}{m}$；距离不相等，平衡的余地反而更大。严格的证明要用到一个关于平均数的不等式，放在附录三。

还可以证明，在“随机拿掉一条边、再沿路做最大耦合、用并集上界估计”这一类办法里，祺乐的平衡式是唯一最好的选法。不过对某些具体的表，还有比它更好的办法。第二十三章会讲到一个例子：四个顶点只有两种回答时，平衡式给出的上限是 $\frac{13}{9}$，而另一种办法能做到 $1$。

所以，任何圈上的任何一组表，倍数都不会超过 $2-\frac{2}{n}$。祺乐翻回作业本背面那排圈，在每个圈下面写了一个数：三角形 $\le \frac{4}{3}$，正方形 $\le \frac{3}{2}$，五边形 $\le \frac{8}{5}$，六边形 $\le \frac{5}{3}$。正方形下面那个数，和第八章的“至少 $\frac{3}{2}$”正好碰上。