《CM》1.2 Lines In The Plane

1.2 Lines In The Plane 平面中的直线

问题:n条直线最多可以把一个平面划分成多少个区域?把这个数值记作Ln。显然L0 = 0, L1 = 2, ...

注意到,一条直线最多能把一个区域分成2个区域,如果我们放一条直线,使他经过所有原来的区域,这样得到的总区域个数必然最大,为原来区域数的两倍。但是,这是做不到的!不难发现,当这条直线经过原先的k个区域时,它与原先的直线交于k-1个不同的点(因为每个交点都处于两个相邻区域的边界,所以只有k-1个交点)!只要我们适当放置这条直线,使得它和原来的直线全都相交(并且这显然可以做到),然后适当移动位置(平移),使得不和原先的交点重合(这也可以做到),这样就能得到最大的区域数了!这就是说

L0 = 1;
Ln = Ln-1 + n, for n>0.

同样,我们不依赖打表找规律的方法来求解closed form,我们对这个递归式进行展开:

Ln = Ln-1 + n
= Ln-2 + (n-1) + n
...
= L0 + 1 + 2 + ... + n
= 1 + Sn.

其中Sn是一个首项为1公差为1的等差数列,很容易得出

Ln = 1 + n(n+1)/2, for n≥0.

现在,考虑该问题的一个变形,如果是n条折线呢?最多能划分多少区域?用Zn表示这个数。同样,Z0 = 1, Z1 = 2, ...

注意到,每条折线其实可以看成是两条直线相交,但在交点其中一侧不延伸。这样,在不延伸的那一侧,我们至少会损失2个区域,这就是说,每个折点最少损失2个区域!我们可以适当放置折线,让折点在“外侧”(适当的远),并且每条直线都相交不同的点,这样每个折点就只少了2个区域,这正是我们总共失去的区域数,于是

Zn = L2n - 2n = 2n2 - n + 1, for n≥0.



3 thoughts on “《CM》1.2 Lines In The Plane

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*