第十二章上界碰到下界

这个上界不能再小。证明的办法，就是把第八章的逐一缺失推广到 $n$ 个顶点。

推广逐一缺失

$n$ 个顶点要用 $n$ 种回答，四个去处不够用；五边形更不可能由删记录得到。所以这一节去掉名字，直接给回答编号。

圈上有 $n$ 个顶点，回答也有 $n$ 种，编号 $1$ 到 $n$。第 $i$ 个顶点的表不许出现第 $i$ 种回答，其余 $n-1$ 种平分，每种 $\frac{1}{n-1}$。

相邻两个顶点 $i$ 和 $j$ 的表，只在第 $i$ 种和第 $j$ 种回答上不同，各差 $\frac{1}{n-1}$。全变差距离是 $\frac{1}{2}\times \frac{2}{n-1}=\frac{1}{n-1}$。

和第八章一样，每张签上 $n$ 个顶点的回答不可能全相同，所以绕圈一周至少有两条边两端不同。$n$ 条边不同的机会加起来至少是 $2$，其中最大的至少是 $\frac{2}{n}$。和它的距离 $\frac{1}{n-1}$ 相比，倍数至少是 $$\frac{2/n}{1/(n-1)}=\frac{2(n-1)}{n}=2-\frac{2}{n}$$

下界正好撞上了上一章的上界。所以

$$c(C_n)=2-\frac{2}{n}$$

上界和下界碰在一起，叫作锐界。“锐”是说这个上界已经不能再改小，换成任何更小的数，都能找到一组表，怎样安排也做不到这么小的倍数。

三角形是 $\frac{4}{3}$，正方形是 $\frac{3}{2}$，五边形是 $\frac{8}{5}$，六边形是 $\frac{5}{3}$……圈越长，这个数越接近 $2$，但任何一个有限长的圈都还小于 $2$。

“越长越难”只是就最坏情况说的，大圈上的某一组表，可能比小圈上的表还容易。

小小的改动，同样的倍数

逐一缺失的表里，相邻两边的距离并不小。正方形上是 $\frac{1}{3}$：每删一条记录，单独安排也至少有三分之一的机会要换地方。

瀚林看着那四张表，说：“真删一条记录，表一般只变一点点吧。”

我们当时都这样想过。如果每张表都和别的表非常接近，这种互相牵制会不会小到可以不管？

祺乐在正方形上加了一个新的回答：在家歇着，记作 $★$。它不算去处，只在这一章出现。设想一个很“宅”的助手，大多数时候都劝你“周六就在家歇着吧”，只有 $\frac{1}{5}$ 的时候才建议出门；出门的那一小截里，才是第八章那道难题，每种情况各有一个去处绝对不去：

每一行是 $\frac{4}{5}$ 加上三个 $\frac{1}{15}$，正好是 $1$。相邻两种情况只在两个去处上各差 $\frac{1}{15}$，距离是 $\frac{1}{15}$，比原来的 $\frac{1}{3}$ 小多了。

去掉名字，一般地说。在 $n$ 个顶点的逐一缺失上，给所有顶点加一种共同的新回答 $★$。每张表改成：有 $1-\epsilon$ 的机会是 $★$，剩下 $\epsilon$ 的机会才按原来的逐一缺失分配。$\epsilon$ 是希腊字母，读作“艾普西龙”，这里代表一个可以很小的正数，比如百分之一。

这样一来，相邻两张表的距离缩小成 $\frac{\epsilon }{n-1}$，所有的表都非常接近“几乎总是 $★$”。

可是，所有顶点只有在全都写 $★$ 的时候才可能相同，而这件事的机会最多是 $1-\epsilon$。所以至少有 $\epsilon$ 的机会，圈上的回答不全相同，这时至少有两条边不同。各边不同的机会加起来至少是 $2\epsilon$，最大的那条至少是 $\frac{2\epsilon }{n}$，倍数仍然至少是 $\frac{2\epsilon /n}{\epsilon /(n-1)}=2-\frac{2}{n}$。

这个下限也做得到：先以 $1-\epsilon$ 的机会让所有顶点写 $★$；否则就用第八章“挑一个特殊顶点”的抽法。每条边不同的机会恰好是 $\frac{2\epsilon }{n}$。

祺乐把正方形的数代进去：$\epsilon =\frac{1}{5}$，距离是 $\frac{1}{15}$，最好的安排下每条边不同的机会是 $\frac{1}{10}$。两个数都很小。瀚林拿 $\frac{1}{10}$ 除以 $\frac{1}{15}$，得 $\frac{3}{2}$。

对这个很“宅”的助手，删一条记录，回答几乎不变，大多还是“在家”；可是最坏的那一步，还是要多付一半。

瀚林不太甘心，把 $\epsilon$ 换成百分之一又算了一遍：距离 $\frac{1}{300}$，最好的安排 $\frac{1}{200}$，除出来还是 $\frac{3}{2}$。