返回题库

平面分割

Plane Partition

专题
Discrete Math / 离散数学
难度
L4

题目详情

用 10 条两两不平行的直线来分割平面。问：最多能把平面分成多少个互不相交的区域？（例如 1 条直线能分成 2 个区域。）

英文原题

Determine the maximum number of disjoint regions into which the plane can be divided by 1010 non-parallel lines. For instance, a single line divides the plane into 22 regions.

解析

要使区域数最大，除“两两不平行”外还应让任意三条直线不共点（一般位置）。

此时第 nn 条直线会与前 n−1n-1 条直线产生 n−1n-1 个交点，把自己分成 nn 段，从而新增 nn 个区域。

递推：R0=1R_0=1，Rn=Rn−1+nR_n=R_{n-1}+n，因此

Rn=1+∑k=1nk=1+n(n+1)2.R_n=1+\sum_{k=1}^n k=1+\frac{n(n+1)}{2}.

代入 n=10n=10 得

1+10⋅112=56.1+\frac{10\cdot 11}{2}=56.

英文解析

In order to maximize the number of areas, any three straight lines should not be common (general position) in addition to "two two not parallel".

At this point, the nn line will create n−1n-1 intersections with the previous n−1n-1 lines, dividing itself into nn segments, thus adding nn areas.

Recursion: R0=1R_0=1, Rn=Rn−1+nR_n=R_{n-1}+n, therefore

Rn=1+∑k=1nk=1+n(n+1)2.R_n=1+\sum_{k=1}^n k=1+\frac{n(n+1)}{2}.

Substitute n=10n=10 to get

1+10⋅112=56.1+\frac{10\cdot 11}{2}=56.