《入门经典》——6.19

  问题:你有一块椭圆的地。你可以在边界上选n个点,并两两连接得到n(n-1)/2条线段。他们最多能把土地分成多少部分?

  分析:容易想起来我们在《具体数学》第一章遇到的折线分平面问题,但是这里并不需要你求最多的交点数而是最多的分割平面数,二者必然有着联系,我们可以基于最多交点的递推关系尝试找分割平面的递推关系,理论上是可行的,但是这里是递推套着递推,显得有点难操作。

尝试进行平面到空间的转化。

  我们先将椭圆最外围的n个平面去掉,将得到的平面图形当中的交点“升起来”,这样我们将得到一个简单几何体,基于几何学中的欧拉公式V-E+F = 2,同时看到我们应该去掉n个顶点构成的“底面”,同时不要忘记我们刚才去掉的n个面,所以这道问题的最终答案是基于这个转化过后的几何体的V、E,即:

V-E+1+n.

  那么现在我们面临的问题便是,如何找到这个几何体的V和E,基于转化的等价性,我们不妨再次回到平面图形进行分析,V即有n个起始点和所有交点的和,E即所有的连线被切成的段数,想计算他们既需要一定的组合计数的功底。

   我们采取的策略是从某个固定点A开始,连接A剩余任意一点得到线段a,我们讨论线段a左右两侧的点的个数来进行计数。

   对于V,对于某个固定点,然后遍历固定点和其余点的连线,该连线上会有∑i(n-2-i)个交点(能够看到这里这样计算是认为任意三个线段不相交,这其实与题设中“最多”的限制条件相呼应的),同时对一开始的固定点我们也需要进行遍历,即n∑i(n-2-i),这里需要注意的时候,对于固定点A连接的某个对角线a,其另一个端点是B,那么遍历固定点到B的时候,边会被重复计算2次,因此点会被重复计算2次,同时对于a上的交点,它不仅在a上,还在另外一条边上,因此该点又被重复计算了2次,综上得出结论,点被重复计算了4次。即V由如下公式进行计算:

   对于E,我们基于上面的得到枚举出的对角线上的点,我们得到该对角线被分成i(n-2-i) + 1端,但是边重复记了2次,因此E有如下公式进行计算:

 

  即记f(n)为该题的解,有如下计算公式:

 

  ps:其实这里基于平面图我们从平面图的角度来看,也可以直接应用欧拉公式,这样略去了等价转化过程。在二者(几何体-平面图)的过渡其实就是上文我们模拟的过程,只不过方向不同,人们常常将几何体进行投影变成平面图,而上文我们尝试将平面图“延展”成几何体。但是两个过程都需要面临边界弧线这个令人不快的情形。关于这两种情况的欧拉公式的证明笔者在《数学证明》的专栏中给出。

原文地址:https://www.cnblogs.com/rhythmic/p/5598669.html