关于二维情况下另类切蛋糕问题的思路

参考源：3Blue1Brown：【官方中配】分圆问题，诡异的数列规律：解答篇

这个情况下，我们不再考虑切几刀，而是圆周上有n个点，每一刀的刀痕都必须通过圆周上这n个点中的两个点的情况。求最大分割数。
这个问题有一个非常有趣又诡异的答案
当只有1个点的时候，最多只能有 $1$ 个区域
当有2个点的时候，最多可以分成 $2$ 个区域
当有3个点的时候，最多可以分成 $4$ 个区域
当有4个点的时候，最多可以分成 $8$ 个区域
当有5个点的时候，最多可以分成 $16$ 个区域
似乎是非常简单的规律，然而：
当有6个点的时候，最多只能分成 $31$ 个区域了，差一个就满足 $2^{n - 1}$ 的规律了，但已经不太对了
当有7个点的时候，最多只能分成 $57$ 个区域了，差的有点多
当有8个点的时候，最多是 $99$ 个区域
当有9个点的时候，最多是 $163$ 个区域了
然而，后面又出现一个巧合，
当有10个点的时候，最多是 $256$ 个区域了，虽然不是 $2^{9} = 512$ ，但是 $2$ 的幂再次出现

解题主要的思路是根据欧拉示性数公式（Euler’s Characteristic Formula）：V-E+F=2
解释一下这个公式，这是指在联通的平面图（Planar graph）上，顶点的个数-边的调数+平面区域的个数=2
举个例子：
下图中有5个顶点，8条边，5个平面区域（其中第五个区域是环绕1234区域的无限大平面）
关于二维情况下另类切蛋糕问题的思路
欧拉公式的证明这里不给出

因为切蛋糕问题也可以变成一个平面图问题，我们为了得到蛋糕可以分成的块数，即F，只剩下了两步：

求出平面图中顶点的个数
我们需要判断是否有多条切痕交于一个点的情况，但如果多条切痕交于圆内同一点，其实会导致能够产生的平面区域数量减少，举一个简单的例子如下：第一张图中心区域由于三切痕交于圆内一点，相比第二张图少了一个区域。

那么，我们就从任意三条切痕都不交于圆内同一点的情况进行讨论
观察下面这张图，我们发现，任意一个交点（橙色箭头）对应圆周上的四个点（红色剪头），换而言之，对于边上有n个点的情况而言，图中将会有 $C_{n}^{4}$ 个交点，此外还有 $n$ 个交点是本身存在的，所以图中的总顶点数表示为：
$V = C_{n}^{4} + n$
求出平面图中边的个数
如果仅仅将切痕和圆周看作边，原本就存在的顶点看作图的顶点的话，图中的边其实是相交了的，这就不能算是平面图了。所以我们将这些刀痕的交点也算作是图的顶点。我们就得到了一张平面图。
如何计算边的条数呢？
在图论中，有一个度（degree）的概念，对于无向图来说（这篇博文中的内容都是无向图），一个顶点的度数定义为与该顶点相连的边的条数。由于任意三条刀痕都不交于圆内的同一点，所以圆内的所有交点由且仅由两条切痕构成，所以这些点的度数是4，而圆周上的n个点中，由于每个点都会与其他n-1个点相连，而与最近的两个点会连接两条边（一条是切痕，另一条是圆周），所以每个点的度数都是n+1
所以图中的总度数表示为 $D e g r e e = 4 * C_{n}^{4} + n (n + 1)$

度数跟边的关系非常简单，由于在无向图中，每条边都会给两个顶点各贡献一个度，所以无向图中边数就等于总度数的一半

\begin{aligned} E & = 2 * C_{n}^{4} + \frac{n (n + 1)}{2} \\ = 2 * C_{n}^{4} + C_{n + 1}^{2} \\ = 2 * C_{n}^{4} + C_{n}^{2} + C_{n}^{1} \end{aligned}

根据欧拉示性数公式，

\begin{aligned} F & = E - V + 2 \\ = (2 * C_{n}^{4} + C_{n}^{2} + C_{n}^{1}) - (C_{n}^{4} + n) + 2 \\ = C_{n}^{4} + C_{n}^{2} + 2 \end{aligned}

当然，由于这个F是考虑了圆外的那片无限大空间的，所以真实的结果还要减一，答案是：

C_{n}^{4} + C_{n}^{2} + C_{n}^{0}

这个时候，我们结合帕斯卡三角（或者说杨辉三角）来看待最前面的那个诡异的现象是如何产生的。
因为 $C_{n}^{m} = 0, m > n$
所以最好的方法是将三角写成如下矩阵，且行列都从0开始计数：
除去第0行，每个数都由其上方与左上方的数相加而得

\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots \\ 1 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots \\ 1 & 3 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \dots \\ 1 & 4 & 6 & 4 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & \dots \\ 1 & 5 & 10 & 10 & 5 & 1 & 0 & 0 & 0 & 0 & 0 & \dots \\ 1 & 6 & 15 & 20 & 15 & 6 & 1 & 0 & 0 & 0 & 0 & \dots \\ 1 & 7 & 21 & 35 & 35 & 21 & 7 & 1 & 0 & 0 & 0 & \dots \\ 1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1 & 0 & 0 & \dots \\ 1 & 9 & 36 & 84 & 126 & 126 & 84 & 36 & 9 & 1 & 0 & \dots \\ 1 & 10 & 45 & 120 & 210 & 252 & 210 & 120 & 45 & 10 & 1 & \dots \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋱ \end{matrix}

当

n \leq 5

时，由于答案是

C_{n}^{4} + C_{n}^{2} + C_{n}^{0}

，我们每次都取了偶数列（第0、2、4列），由于第

i

行的和是

2^{i}

，所以该行偶数项的和为

2^{i - 1}

但是从

n = 6

开始，矩阵的第6列开始有值，我们只取到第4列，没有将偶数列全部算进来，所以不再满足

2

的幂次的规律
那为什么

n = 10

的时候，答案是

2^{8} = 256

呢，因为第十行的2、4列，由第九行的1、2、3、4列相加得到，而第十行的第0列等于第9行的第0列。即第十行的0、2、4列恰好是第九行的0、1、2、3、4列的和，恰好是第九行的前一半，而帕斯卡三角又有对称性，所以结果恰好是第九行和的一半，即

2^{8}

关于二维情况下另类切蛋糕问题的思路

相关推荐