问题:

一条项链上有 $n$ 种类型的珠宝,每种珠宝的数量均为偶数。问至少需要切几刀,可以将所有珠宝均分?


首先介绍 Borsuk-Ulam Theorem

想象一个三维空间中的球面被扭曲压缩到二维平面上,由于变形是连续的,因此球面上有许多点重合在了一起。Borsuk-Ulam 定理告诉我们总能找到这样的两个点,它们一开始在球面上处于完全相反的两极,经过映射后会重合在一起。

这一定理有一个经典的应用:地球上一定存在完全相对的某一对点,两处的气温和气压都恰好相同。因为地球上的每一点都对应着气温和气压两个值,这与将地球表面连续映射到二维坐标系上是一样的。

简单证明:

给定某个从球面到平面的连续函数 $f(x)$,我们的目标既是证明存在 $p$ 使得 $f(p) = f(-p)$。

定义 $g(x) = f(x) - f(-x)$,不难看出 $g$ 也是连续的并且是奇函数(关于原点对称)。此时我们只需证明球面上存在点 $p$ 使得 $g(p) = 0$ 即可。

考虑当点 $p$ 在球面“赤道”上行进一圈时,$g(p)$ 会在平面上形成某种闭合回路,由于 $g$ 关于原点对称,则该回路必经过原点或包围原点。若其经过原点,则证明完毕。若包围原点,想象球面上的大圈连续收缩至“极点”时,对应平面上的闭合回路也必定会连续收缩至某一点。因此必定存在某一时刻,$g(p)$ 经过原点,证明完毕。

Sphere to Plane
Sphere to Plane

为了阐述该定理如何应用到我们的问题上,首先将 Borsuk-Ulam 定理更严格写出:

$$ \begin{gather*} \text{For any continuous function } f: S^2\to \mathbb{R}^2 \\ \exists (x_1,x_2,x_3) \quad\text{s.t. } x_1^2+x_2^2+x_3^2=1 \\ f(x_1,x_2,x_3) = f(-x_1,-x_2,-x_3) \end{gather*} $$

由于该定理适用于连续情况而项链分赃问题是离散的,首先我们将宝石想象为连续的线段。可以看出如果这一连续的问题能够解决,则离散的问题也自然解决。因为我们可以调整切割点的位置使其正好落在线段端点上。

考虑仅有 $2$ 种宝石的情况,令项链长度为 $1$ ,欲将球的方程与切割方法联系起来,令切割的三段长度分别为 $x^2, y^2, z^2$ ,并依据正负号决定将这一段长度分给 $A$ 或 $B$ 。这样就有 $x^2+y^2+z^2=1$ ,即球面上的每一点都对应一种分配方案。

更进一步地,我们构造这样的函数:输入一个给定的项链分配方案,输出两个数,分别对应其中一人得到的两种宝石数量。这其实就是从球面到平面的一个映射。由 Borsuk-Ulam 定理可知,一定存在一种分配方案使得 $A、B$ 在交换所分得的宝石后保持每种数量不变,也就是一种均分方案。

将这一定理拓展至高维情形:从一个 $n$ 维空间的超球面到 $n-1$ 维空间的连续映射也必须保证这样一对点的存在。因此对于 $n$ 种不同的宝石,只需要切 $n$ 刀便可进行均分。

参考

  1. Video
  2. Borsuk-Ulam Theorem