第十七章不能再拆的角落

切层以后，一组输入就由一串权重 ${\lambda }_S$ 描述。权重都不能是负数；对每个顶点，包含它的那些集合的权重加起来恰好是 $1$。

满足这些条件的所有权重组合，放在一起构成一个“容器”，论文里记作 ${\Lambda }_n$。

先看两个顶点

两个顶点时，非空集合只有三个：$\{1\}$、$\{2\}$、$\{1,2\}$。条件是 $${\lambda }_{\{1\}}+{\lambda }_{\{1,2\}}=1,{\lambda }_{\{2\}}+{\lambda }_{\{1,2\}}=1$$ 所以只要定下 ${\lambda }_{\{1,2\}}$，另外两个就都等于 $1-{\lambda }_{\{1,2\}}$。${\lambda }_{\{1,2\}}$ 可以取 $0$ 到 $1$ 之间的任何数，整个容器就是一条线段。

线段有两个端点。一个端点是 ${\lambda }_{\{1,2\}}=1$：两个顶点共有全部的机会，也就是两张表完全一样。另一个端点是 ${\lambda }_{\{1,2\}}=0$：两个顶点完全没有共同的部分。线段中间的任何一点，都可以看成这两个端点的“混合”：比如 ${\lambda }_{\{1,2\}}=\frac{1}{3}$，就是先抽一张签决定用哪个端点。签盒里放三张签，一张写“第一个端点”，两张写“第二个端点”，抽到哪个就照哪个去做。

混合与角落

一般地，两组合法的权重可以混合：先抽一张签，决定这一次用哪一组，再照那一组去做。平均下来的权重仍然合法，因为每个顶点的总和仍然是 $1$。

如果一组权重不能写成两组不同合法权重的混合，就叫它容器的一个“角”。线段的两个端点是角，中间的点都不是。

放回周末的小世界，一组权重就相当于一套签盒，每种情况一个。两套签盒混合，就是先抽一张签，决定这一次用哪一套。没法拆成两套不同签盒混合的那一套，就是一个角。

想象一个三角形：三角形里面的任何一点，都可以由三个角按一定比例混合得到；可三个角本身，不能由三角形里别的点混合出来。我们的容器维数高得多，但道理一样：每一组合法的权重，都可以写成若干个角的混合。

三个顶点的六个角

三个顶点时，最简单的一类角是“分组”：把三个顶点不重不漏地分成几组，每一组给权重 $1$，其余集合给 $0$。每个顶点恰好在一组里，所以合法。分组的方法有五种：

• 三个人一组：$\{1,2,3\}$；
• 两人一组、一人单独：$\{1\}\{2,3\}$，$\{2\}\{1,3\}$，$\{3\}\{1,2\}$；
• 各自单独：$\{1\}\{2\}\{3\}$。

还有一个角不是分组：三个“对子” $\{1,2\}$、$\{1,3\}$、$\{2,3\}$ 各给权重 $\frac{1}{2}$。每个顶点恰好出现在两个对子里，$\frac{1}{2}+\frac{1}{2}=1$，合法。它不能拆成别的合法权重的混合，也是一个角。三个顶点一共就这六个角。

上一章的例子，正好是三个角的混合：以 $\frac{1}{2}$ 的机会选“三人一组”，以 $\frac{1}{4}$ 的机会选“$\{1\}$ 单独、$\{2,3\}$ 一组”，以 $\frac{1}{4}$ 的机会选“$\{1,2\}$ 一组、$\{3\}$ 单独”。平均下来，$\{1,2,3\}$ 得到 $\frac{1}{2}$，$\{1\}$、$\{2,3\}$、$\{1,2\}$、$\{3\}$ 各得到 $\frac{1}{4}$，和那张权重表完全一样。

对“分组”这种角，共同安排非常简单：每个顶点就回答它所在的那一组。把三种分组按 $\frac{1}{2}$、$\frac{1}{4}$、$\frac{1}{4}$ 混合，再用上一章“变回去”的办法：

• 选中“三人一组”时（机会 $\frac{1}{2}$），三个顶点一起看同一枚硬币，得到 $000$ 或 $111$；
• 选中 $\{1\}\{2,3\}$ 时（机会 $\frac{1}{4}$），顶点 $1$ 回答 $0$，顶点 $2$、$3$ 回答 $1$，得到 $011$；
• 选中 $\{1,2\}\{3\}$ 时（机会 $\frac{1}{4}$），得到 $001$。

最后四种三栏签 $000$、$111$、$011$、$001$ 各占 $\frac{1}{4}$。三栏取 $1$ 的机会分别是 $\frac{1}{4}$、$\frac{1}{2}$、$\frac{3}{4}$，正是原来的表；任意两栏不同的机会，都正好等于它们的全变差距离。数一数这四张签就能验证。

这四张签，用第四章那根长度为 $1$ 的绳子也抽得出来。在绳子上随手点一个位置：落在前 $\frac{1}{4}$，写 $111$；落在 $\frac{1}{4}$ 到 $\frac{1}{2}$ 之间，写 $011$；落在 $\frac{1}{2}$ 到 $\frac{3}{4}$ 之间，写 $001$；落在最后 $\frac{1}{4}$，写 $000$。三个顶点共用同一个点，每个顶点只看这个点是不是落在它自己回答 $1$ 的机会以内，也就是它去电影院的那一截。这种共用一个点的抽法，第二十三章还会用到。

为什么一个角最多用 $n$ 个集合

清单能不能变得有限，要看这一步。韵吉在本子上写了一个问题：一个角上，权重不为零的集合最多有几个？后来韵吉也拿这个问题问过 AI。

回到两个顶点的线段。线段中间的点，三个集合的权重都是正的。比如 ${\lambda }_{\{1,2\}}=\frac{1}{2}$、${\lambda }_{\{1\}}={\lambda }_{\{2\}}=\frac{1}{2}$。这时我们可以把 ${\lambda }_{\{1,2\}}$ 加上一点点 $t$，同时把 ${\lambda }_{\{1\}}$ 和 ${\lambda }_{\{2\}}$ 各减去 $t$。两个顶点的总和都不变，仍然合法。$t$ 可以取正的，也可以取负的。于是这一点就落在两组合法权重的正中间，是它们的混合，所以不是角。

三个顶点也能这样挪。上一章切出的那组权重，五个集合都是正的：$\{1,2,3\}$ 是 $\frac{1}{2}$，$\{1,2\}$、$\{2,3\}$、$\{1\}$、$\{3\}$ 各是 $\frac{1}{4}$。把 $\{1,2,3\}$ 加上 $t$，同时把 $\{1,2\}$ 和 $\{3\}$ 各减去 $t$。顶点 $1$ 的集合是 $\{1,2,3\}$、$\{1,2\}$、$\{1\}$，一加一减，总和不变；顶点 $2$ 的是 $\{1,2,3\}$、$\{1,2\}$、$\{2,3\}$，顶点 $3$ 的是 $\{1,2,3\}$、$\{2,3\}$、$\{3\}$，也都是一加一减。

$t$ 取 $\frac{1}{4}$，得到 $\{1,2,3\}$ 为 $\frac{3}{4}$，$\{1\}$、$\{2,3\}$ 各为 $\frac{1}{4}$，$\{1,2\}$ 和 $\{3\}$ 变成 $0$。$t$ 取 $-\frac{1}{4}$，得到 $\{1,2,3\}$ 为 $\frac{1}{4}$，$\{1,2\}$、$\{3\}$ 各为 $\frac{1}{2}$，$\{1\}$、$\{2,3\}$ 仍是 $\frac{1}{4}$。两组都合法，每个顶点加起来都是 $1$，原来那组正好在它们中间，所以它不是角。

这组权重能挪，是因为正的集合有五个，顶点只有三个。一般地，在一个角上，权重为正的集合最多 $n$ 个。而且在一个角上，这些正权重被方程组唯一确定，一点也挪不动。

于是，每个角对应的那组输入，最多只用到 $n$ 种“回答”。而且角的数目是有限的：选哪几个集合当正权重，只有有限种选法，每种选法最多对应一个角。