这个问题来自具体数学第一章的一个作业题,由于资料太少,困扰了我很久,昨天终于想通了,所以想分享一下

这个问题的描述是这样的:

在一块奶酪上划出五道直的切痕,可以得到多少块奶酪?(在你划切痕时,奶酪必须保持在它原来的位置上,且每道切痕必定与三维空间中的一个平面相对应。)

这个问题简单来说,就是一块蛋糕切5刀最多可以得到几块蛋糕。(对了,还有个人要请我吃蛋糕的!)

经过大量的资料查询,最终发现这个问题是一个 Hyperplane Arrangements(超平面分割) 的问题,这里是三维平面,Richard P. Stanley在它的文章中提到了公式。

    f_{n}(k) = \displaystyle\sum_{j=0}^n{k \choose j}

其中f_{n}(k)n维空间中切k刀可以得到的区域数。拿这个例子来说,不!我们还是切4刀吧!5刀实在是太让人困惑了

\begin{alignedat}{1}
    f_{3}(4) &= {4 \choose 0} + {4 \choose 1} + {4 \choose 2} + {4 \choose 3} \\
    &= 1 + 4 + 6 + 4 = 15
\end{alignedat}

答案是15!就是说一块蛋糕切4刀最多可以得到15块蛋糕,你想到了吗?这里有一张来自维基百科的图片,可能对你有用(如果你真的很想知道是怎么切的,后面我们将给出更好的方法):

好了,我们现在已经有一些直观的理解了,现在考虑,怎么样切才是最多的,为了便于找出规律,我们应该首先从更低维度的空间去探索。

首先,我们考虑零维空间:0维空间不管怎么切,都是一个区域,似乎没有什么用。

那么,一维度空间会是怎么样的呢?
一维空间就是说,在一条直线上,用5个点(这里是对应5刀),能把线段分成几个区域,显然,只要任意两个点不重复,就可以得到最大值6。

现在,考虑二维空间
同样的,二维空间中就是说,在一个平面上,用5条直线可以可以把平面分成几个区域,这个也相当简单,只要任意三条直线不相交于同一点上,并且两两相交(没有平行的线),就可以得到最大值16。

三维空间(就是说,在一个空间中,用5个平面可以将这个空间分成多少区域)我们可以猜测出一些类似的最大区域条件,尽管我们现在不能证明它:

  • 任意两个平面不平行
  • 任意三个平面交于一点
  • 任意四个平面不相交于一点

我们考虑递归方程,就有:

    f_{3}(5) = f_{3}(4)+f_{2}(4)

因为在三维空间中切5刀等于先在三维空间中切4刀,也就是式子的第一部分f_{3}(4),然后再切1刀,式子的第二部分f_{2}(4)。为什么是f_{2}(4)呢?这是因为后面这1刀将会与前面4刀相交,在该平面中产生4条交线,这4条交线在该平面内每划分一个区域就会在空间中多划分一个区域,并且只要这5个平面满足上面三维空间中最大区域的全部条件,就一定会满足二维空间中最大区域的条件,得到最大值。

现在我们就证明了上面三维空间最大区域的条件,并且,我们进行推广可以得到更加有用的东西:

    f_{n}(k) = f_{n}(k-1)+f_{n-1}(k-1)

当且仅当

  • 任意两个n-1维空间不平行
  • 任意n个n-1维空间交于一点
  • 任意n+1个n-1维空间不相交于一点

使用数学归纳法很容易证明这一点,这里就不做证明了,如果把该递归式化简成封闭形式就可以得到Richard P. Stanley的公式。

分类: 计算机科学