【具体数学 Concrete Mathematics】1.1.2 平面上的直线-育师

对应《具体数学：计算机科学基础（第 2 版）》第 1 章 §1.2，书内第 4—7 页。本文沿用专栏的三级编号。

在平面上画n nn条直线，最多能划分出多少个区域？乍一看，这像是一个需要不断画图、数格子的问题。真正有用的观察是：先别数所有区域，只看新画的一条线能增加多少个。

1. 前三个数，可能把人带错方向

设最大区域数为L n L_nLn。没有直线时，整个平面就是一个区域，所以L 0 = 1 L_0=1L0=1。

一条直线得到两个区域；两条相交直线得到四个区域。由1 , 2 , 4 1,2,41,2,4猜测L n = 2 n L_n=2^nLn=2n很自然，但第三条直线就会推翻它：三条直线最多得到7 77个区域。

原因是新直线虽然能够切开一些旧区域，却未必经过每一个旧区域。不能把“经过的区域会被切成两块”直接理解为“总区域数翻倍”。

直线数n nn	0 00	1 11	2 22	3 33	4 44	5 55
最大区域数L n L_nLn	1 11	2 22	4 44	7 77	11 1111	16 1616
相比前一步增加	—	1 11	2 22	3 33	4 44	5 55

相比第一行，第二行已经把规律展示得相当清楚。

2. 第n nn条直线，至多增加n nn个区域

在已有n − 1 n-1n−1条直线的图形中加入一条新的、与旧线不重合的直线。

它与每条旧直线最多相交一次，因此最多产生n − 1 n-1n−1个不同的交点。这些交点把新直线切成至多n nn段，其中两端的“段”是向无穷远延伸的射线。

例如，新直线上有三个不同交点时，可以把沿线的位置理解为：

区域 A ----×---- 区域 B ----×---- 区域 C ----×---- 区域 D

为什么这些线段对应不同的旧区域？由直线划出的每个区域都是凸集：区域内任取两点，它们之间的整条线段也在区域内。因此，一条直线不能离开某个区域后又重新进入它。

每经过一个旧区域，新直线就把它分成两部分，区域总数增加1 11。所以第n nn条直线至多增加n nn个区域，即：

L n ≤ L n − 1 + n . L_n\le L_{n-1}+n.Ln≤Ln−1+n.

重合线不会产生新的区域，当然也不会超过这个上界。

3. 上界什么时候能取到？

要让新直线上确实出现n − 1 n-1n−1个不同交点，必须避免两个情况：

新直线与某条旧线平行，否则少一个交点。
新直线经过旧线之间已有的交点，否则原本不同的交点合并了。

逐条加入直线时，总能避开有限个旧方向和旧交点。于是可以使所有直线满足任意两条不平行，任意三条不共点，通常称为处于一般位置。

此时上界可以达到，得到：

L 0 = 1 , L n = L n − 1 + n ( n ≥ 1 ) . \boxed{L_0=1,\qquad L_n=L_{n-1}+n\quad(n\ge1).}L0=1,Ln=Ln−1+n(n≥1).

注意，这描述的是“最大区域数”，并非任意画法的区域数。例如三条互不重合的平行线只有4 44个区域；三条不同直线交于同一点则只有6 66个区域。

4. 展开递归式，让增量累加起来

把递归式反复代入：

L n = L n − 1 + n = L n − 2 + ( n − 1 ) + n = L 0 + 1 + 2 + ⋯ + n = 1 + ∑ k = 1 n k . \begin{aligned} L_n &=L_{n-1}+n\\ &=L_{n-2}+(n-1)+n\\ &=L_0+1+2+\cdots+n\\ &=1+\sum_{k=1}^{n}k. \end{aligned}Ln=Ln−1+n=Ln−2+(n−1)+n=L0+1+2+⋯+n=1+k=1∑nk.

设S n = 1 + 2 + ⋯ + n S_n=1+2+\cdots+nSn=1+2+⋯+n。将这一列数与倒序的一列相加，每一对都是n + 1 n+1n+1，共有n nn对，因此：

2 S n = n ( n + 1 ) . 2S_n=n(n+1).2Sn=n(n+1).

代回去便得到封闭形式：

L n = 1 + n ( n + 1 ) 2 . \boxed{L_n=1+\frac{n(n+1)}{2}.}Ln=1+2n(n+1).

再检查两个地方：n = 0 n=0n=0时结果为1 11；相邻两项相减为

( 1 + n ( n + 1 ) 2 ) − ( 1 + ( n − 1 ) n 2 ) = n , \left(1+\frac{n(n+1)}2\right) -\left(1+\frac{(n-1)n}2\right)=n,(1+2n(n+1))−(1+2(n−1)n)=n,

正好符合递归式。

书中所说的“封闭形式”，在这里可以理解为：用固定数量的标准运算直接表达结果，而不必先列出前面所有项。它是表达式层面的概念，不意味着任意精度的大整数计算都具有常数时间成本。

5. “切比萨”类比有哪些前提？

若把平面换成圆形比萨，每一刀切出一条直的弦，而且切割过程中不移动、不堆叠已有的块，那么也可以达到同样的最大块数。

不过，除了直线不平行、不三线共点，还要让相关交点落在比萨内部。两个切割方向即使延长后相交，交点若在比萨外面，也不会增加饼内的分块数。

例如五刀最多是：

L 5 = 1 + 5 × 6 2 = 16. L_5=1+\frac{5\times6}{2}=16.L5=1+25×6=16.

如果允许堆叠、移动已经切开的块，规则就变了，不能直接套这个模型。

6. 本节的延伸：一条线弯一下，会怎样？

原书还讨论了由两条射线连接而成、只有一个拐点的折线。设n nn条这种折线最多划分出Z n Z_nZn个区域。

一个新的折线与一个旧折线最多有2 × 2 = 4 2\times2=42×2=4个交点。因此第n nn条折线至多与之前的折线产生4 ( n − 1 ) 4(n-1)4(n−1)个不同交点，沿折线至多分成4 ( n − 1 ) + 1 4(n-1)+14(n−1)+1段。每增加一段，区域数至多增加1 11，所以：

Z n ≤ Z n − 1 + 4 n − 3. Z_n\le Z_{n-1}+4n-3.Zn≤Zn−1+4n−3.

这里同样需要“能达到上界”的构造。原书采用的思路是先考虑2 n 2n2n条支撑直线，再把每对直线裁成一条折线：将各拐点安排在它与其他折线的交点之外，就能保留不同折线之间的全部交点。这样裁去延长部分时，每条折线恰好使区域总数减少2 22，得到：

Z n = L 2 n − 2 n = 1 + 2 n ( 2 n + 1 ) 2 − 2 n = 2 n 2 − n + 1 . \begin{aligned} Z_n&=L_{2n}-2n\\ &=1+\frac{2n(2n+1)}2-2n\\ &=\boxed{2n^2-n+1}. \end{aligned}Zn=L2n−2n=1+22n(2n+1)−2n=2n2−n+1.

这种构造说明上界可达；随意画出的折线未必有这么多区域。小规模时，Z 0 = 1 Z_0=1Z0=1、Z 1 = 2 Z_1=2Z1=2、Z 2 = 7 Z_2=7Z2=7。

当n nn很大时，直线的最大区域数约为n 2 / 2 n^2/2n2/2，折线的最大区域数约为2 n 2 2n^22n2，两者之比趋于4 44。多一个拐点带来的效果，不能仅凭“边数翻倍”来猜。

7. 用小程序核对数值

defmax_regions(n:int)->int:ifn<0:raiseValueError("n 必须是非负整数")return1+n*(n+1)//2regions=1forninrange(7):ifn>0:regions+=nassertregions==max_regions(n)print(n,regions)