n条直线最多将平面分为几个部分，以及类似问题

abababa

如题，n条直线最多将平面分为几个部分。这个已经知道答案是$\frac{2+n+n^2}{2}$个部分。我想问这类问题属于哪个具体方面的？
类似的问题如：n个正方形最多将平面分为几个部分，n个等边三角形最多将平面分为几个部分，n个圆最多将平面分为几个部分，n个大圆最多将球面分为几个部分等等。

Czhang271828

$n$ 个大圆最多将球面分为几个部分?

下求解"最多"之情形. 不妨设任一交点只含于两个大圆, 反之可以通过微扰法构造具有更多区域的分割. 由于任一大圆与其余 $n-1$ 个大圆交于两点, 从而总交点数 $V=n(n-1)$, 总边数 $E=n(2n-2)$, 故 $F=E+2-V=n(n-1)+2$.

abababa

Czhang271828 发表于 2022-6-16 21:37
$n$ 个大圆最多将球面分为几个部分?

下求解"最多"之情形. 不妨设任一交点只含于两个大圆, 反之可以通过微 ...

这个答案我到是知道，就这个问题来说，用的是欧拉定理，那个关于点、面、棱数量最后等于2的。这个解法和直线分平面那个还不一样，直线分平面是用的递推法。
另几个用正方形、等边三角形分的，我只是曾经记下来那个问题了，没有答案，而且是不是能推广到用一般的正m边形来分平面，最多能分出几个部分的问题。
所以我想知道这类问题属于哪个具体方面，有没有统一解法之类的。

hbghlyj

page238-241.pdf (131.17 KB, Downloads: 44)

2022-6-17 16:01 Upload

Click on the file to download the attachment

命题人讲座《图论》任韩 著

例 9 （1）一个平面被 $n$ 条直线至多划分成多少个区域?
（2）空间能被 $n$ 个平面至多划分成为多少个单连通区域?
(德国国家队集训题)
方法一 把 (1), (2) 中的数分别记为 $p_{n}$ 和 $s_{n}$. 一个显然的递推公式是: $p_{n+1}=p_{n}+n+1, s_{n+1}=s_{n}+p_{n}$. 从它们的这个关系可以很快得到答案.
但是我们并不在意这个解答 (因为它可能回答不了更加一般的问题). 下面将给出另外一个解答, 它会引导我们思考解决更一般的问题.
方法二 在计数理论中有一个基本原理, 就是将一个计算问题利用一一对应转化成为另外一个计算问题. 第一个问题是: 是否可以将平面的 $p_{n}$ 个部分双射到一个较为容易计算的集合? $n$ 条直线恰好有 $\mathrm{C}_{n}^{2}$ 个交点, 但是每一个交点恰好又是每一个区域的最深点 (又是极端原理!). 没有最深点的区域一定是下方无界的. 这 $n$ 条直线把我们引进的水平直线 $h$ 切成 $n+1$ 段, 这些下方无界的区域可以与这些线段对应. 这样有 $n+1=\mathrm{C}_{n}^{0}+\mathrm{C}_{n}^{1}$ 个区域没有最深点. 所以, 平面被划分成为
$$
p_{n}=\mathrm{C}_{n}^{0}+\mathrm{C}_{n}^{1}+\mathrm{C}_{n}^{2}
$$
个连通区域.
在空间中, 3 个平面作出一个交点, 共有 $\mathrm{C}_{n}^{3}$ 个交点, 每一个定点恰好为一个区域的最深点, 因而有 $\mathrm{C}_{n}^{3}$ 个区域有最深点. 而没有最深点的每一个区域把一个水平平面 $h$ 切割成 $p_{n}$ 部分. 所以, 空间的区域数目为
$$
s_{n}=\mathrm{C}_{n}^{0}+\mathrm{C}_{n}^{1}+\mathrm{C}_{n}^{2}+\mathrm{C}_{n}^{3} .
$$
drawing.svg (1010 Bytes, Downloads: 190)

2022-6-17 16:33 Upload

Click on the file to download the attachment

点评 利用引入一个参考物（水平直线和水平平面）这一方法, 将一个极为困难的凸多面体图的计算问题成功转化成为另外一个计算问题, 技巧实在高！重要之处还在于, 这个方法将结果表达成为一个具有普遍性的形式: $s_{n}=\mathrm{C}_{n}^{0}+\mathrm{C}_{n}^{1}+\mathrm{C}_{n}^{2}+\mathrm{C}_{n}^{3}$, 它引导我们去想象一个更加抽象而困难的问题:
在一个高维空间 $ℝ^{n+1}$ 中, $m$ 个超平面可以将 $ℝ^{n+1}$ 最多划分成为多少个单连通凸区域? 答案是不是
$$
\mathrm{C}_{m}^0+\mathrm{C}_{m}^{1}+\mathrm{C}_{m}^{2}+\cdots+\mathrm{C}_{m}^{n} \text { ? }
$$
如果没有引入水平 “超平面” 的概念和所谓 “最深点” 的观察, 人们对于这一类问题的求解难度是不可想象的.下面是这个问题的延续.
⋯
⋯
⋯
⋯

hbghlyj

本楼转换附件为svg

abababa

hbghlyj 发表于 2022-6-17 15:45
命题人讲座《图论》任韩 著

例 9 （1）一个平面被 $n$ 条直线至多划分成多少个区域?

这楼里所说的问题，就是主楼里第一题那种，直线、平面都是可以无限延伸的。而对于有限的划分图形，比如正方形，等边三角形，正n边形等等，这个方法就不管用了吧，可能还要考虑增加到m个图形以后，是不是还能作出更多划分的问题。
所以这应该不是简单的“多面体”或“平面图”的划分问题，可能复杂得多。

hbghlyj

quora.com/How-many-parts-can-the-n-spheres-divide-a-space-into
it depends on the layout:

starting from 1 sphere
1 sphere would divide space into 2 regions (inside, outside)
2 spheres divide space into 4 (outside A & B, inside only A, inside only B, inside A & B) with overlap, or 3 without
3 spheres divide space into up to 8 with overlap, or 4 without
4 spheres divide space into up to 16 with overlap, or 5 without
5 spheres divide space into 6 without overlap; but with overlapping spheres you encounter the same sort of problem you get on a flat surface with circles when you have more than 3 circles

simple answer:
if they aren't allowed to overlap (or touch) the surfaces - then N spheres divide it into N+1 regions - this is fairly easier to visualize.

not as simple answer:
if overlapping is allowed then each new sphere could divide the previous regions by 2 again thus N spheres dividing it into 2^N regions, however this might require N-1 dimensions, which might be outside the implied limitations of the question.
restricting the solution to 3 dimensions
\[2 + \sum\limits_{k=2}^n ((k-1)(k-2)+2) = \frac{n^3-3n^2+8n}{3}\]

reasoning:
start with a Euler Diagrams and Venn Diagrams using circles (2D-'spheres') - potential problems start when the Venn Diagrams have more than 3 circles - 4 spheres -> 3D arrangement

1 circle -> 2 regions
2 circles -> 4 regions
3 circles -> 8 regions
4 circles -> 14 regions (2 less than 4 spheres)
5 circles -> 22 regions .... basically => n^2 - n + 2
etc

induction proof
Circles: For n = 1, the regions is 2. With k-1 circles, when you add a new circle it will intersect with the previous circles at most at 2(k-1) points, so it will be divided into at most 2(k-1) arcs. Each are split a region into 2 new regions. So the increase in the number of regions is limited to at most 2(k-1). Total number is thus
\[2 + \sum\limits_{k=2}^n 2(k-1) = n^2-n+2\]

Spheres: similar

d-dimension hyper-spheres formula
\[R_d(n) = \begin{pmatrix}n-1\\d\end{pmatrix} + \sum\limits_{k=0}^d \begin{pmatrix}n\\k\end{pmatrix}\]
or
\[R_d(n) = R_d(n-1) + R_{d-1}(n-1)\]
thus
\[R_1(n) = R_1(n-1) + R_{0}(n-1) = n^2 - n + 2\]
and
\[R_2(n) = R_2(n-1) + R_{1}(n-1) = \frac{n^3-3n^2+8n}{3}\]

(hopefully no more typos and other errors)

hbghlyj

zhuanlan.zhihu.com/p/29666391

    n条直线最多能把平面分成几个部分?

Ref:Plane Division by Lines

$$a_n=\frac12(n-1)n+1$$

不解释,而且其实封闭图形正方形,圆形分割也是这个答案.

A077588 Maximum number of regions into which the plane is divided by n triangles.

$a_n = 3n^2 - 3n + 2$ for $n > 0$.

Proof (from Joshua Zucker and N. J. A. Sloane, Dec 01 2017)

Represent the configuration of $n$ triangles by a planar graph with a node for each vertex of the triangles and for each intersection point. Let there be $v_n$ nodes and $e_n$ edges. By classical graph theory, $a_n = e_n - v_n + 2$. When we go from $n$ to $n+1$ triangles, each side of the new triangle can meet each side of the existing triangles at most twice, so $\Delta v_n≔v_{n+1}-v_n⩽ 6n$.

Each of these intersection points increases the number of edges in the graph by 2, so $\Delta e_n≔ e_{n+1}-e_n = 3 + 2\Delta v_n$, $\Delta a_n ≔ a_{n+1}-a_n= 3 + \Delta v_n⩽ 3+6n$.

These upper bounds can be achieved by taking $3n$ points equally spaced around a circle and drawing $n$ concentric overlapping equilateral triangles in the obvious way, and we achieve $a_n = 3n^2 - 3n + 2$ (and $v_n = 3n^2, e_n = 3n(2n-1)$) for $n>0$. QED


Division Problems -- Mathworld

hbghlyj

$n$个四边形最多将平面分成的区域数:
A077591 Maximum number of regions into which the plane can be divided using $n$ (concave) quadrilaterals.
$a_n = 8n^2 - 8n + 2 = 2(2n-1)^2$, $n>0$, $a_0=1$.
[It would be nice to have a proof, or even a reference to a proof. - N. J. A. Sloane, Nov 30 2017]

强调了是凹四边形才能取到最大值

我把$n=1$和$n=2$的情况画出来了:
drawing-1.svg.2022_06_17_16_53_43.0.svg (7.18 KB, Downloads: 150)

2022-6-17 23:58 Upload

Click on the file to download the attachment

————————————————————————————————————————————————————

$n$个凸四边形最多将平面分成的区域数:

artofproblemsolving.com/community/c6h377434p10984052
We draw $n$ convex quadrilaterals in the plane. They divide the plane into regions (one of the regions is infinite). Determine the maximal possible number of these regions.
(last post) Tintarn wrote:

The true answer is $a_n=4n^\color{red}2-4n+2=(2n-1)^2+1$.
It clearly suffices to prove that $a_{n+1}-a_n \le 8n$. But this is clear since each of the four new edges can intersect at most $2n$ of the previously drawn edges and hence "create" at most $2n$ new regions. Finally, it is easy to see that drawing squares slightly rotated around their center achieves this number.

红色的2在原帖误为4
画一个图:

hbghlyj

本楼转换附件为svg
顺便把https://zhuanlan.zhihu.com/p/29666391全文抄录如下:

n个三角形最多能把平面分成几个部分?
Ref:A077588 - OEIS

$a(n) = a(n-1) + 6n - 6;a(1)=2$

解得:

$a(n)=2 - 3 n + 3 n^2$

n个四边形最多能把平面分成几个部分?
Ref:A077591 - OEIS

$a_n=2 (3-2 n)^2$

强调了是凹四边形才能取到最大值

想不出是什么情况,而且链接里参考文献都没有...

n个圆最多能把平面分成几个部分?
Ref:Plane Division by Circles


$a(n)=n^2-n+2$

n个椭圆最多能把平面分成几个部分?
Ref:Plane Division by Ellipses


$a(n)=2(n^2-n+1)$

n 个超平面最多把d维超空间分成几个部分?
Ref:n 个平面最多把 3 维空间分成几个部分?

Ref:d维空间中n刀切蛋糕最多能切多少块?求f(d,n)

$R_d(n)=R_d(n-1)+R_{d-1}(n-1)$

初值条件:

$\left\{\begin{aligned} &R_1(n)=1+n\\ &R_d(1)=2\\ \end{aligned}\right.$

解得: $R_d(n)=\sum _{k=0}^d \binom{n}{k}=2^n-\binom{n}{d+1} \, _2F_1(1,d-n+1;d+2;-1)$

这个结果当然是很有趣的,我们知道分割的平凡上界就是 $2^n$

平面就是太平了,所以受到了某种阻碍,我想不明白后面那个超几何函数代表了什么.

n个超球面最多将D维超空间分成多少个部分?
Ref:N个球面最多将3维空间分成多少个部分?

递推式是一样的...很自然但是其实不那么自然...

$R_d(n)=R_d(n-1)+R_{d-1}(n-1)$

初值条件:

$\left\{\begin{aligned} &R_1(n)=2n\\ &R_d(1)=2\\ \end{aligned}\right.$

解得:

$R_d(n)=\sum _{k=0}^d \binom{n}{k}+\binom{n-1}{d} $

验证了上面的想法,球面比平面要能屈能伸多了...

如果一个几何体可以像橡皮泥一样任意变形定然可以达到上界...

所以这当中起到关键作用的几何量到底是谁呢?

hbghlyj

abababa 发表于 2022-6-17 10:48
这楼里所说的问题，就是主楼里第一题那种，直线、平面都是可以无限延伸的。而对于有限的划分图形，比如正 ...

正$n$边形都是一样的解法.取一个正$n$边形,每次绕着中心旋转很小的角度重叠在一起,就能取最大值.

abababa

hbghlyj 发表于 2022-6-17 18:00
https://zhuanlan.zhihu.com/p/29666391

这个原理知道了，我开始以为不一定能构造出来。但是正m边形的结果不是那个吧，应该是$F_n=mn^2-mn+2$，其中$F_n$表示能划分成的区域的个数，$m$表示正$m$边形，$n$表示用$n$个正$m$边形去划分。而且圆的情况也不一样吧，不能旋转了。

abababa

hbghlyj 发表于 2022-6-17 19:17
正$n$边形都是一样的解法.取一个正$n$边形,每次绕着中心旋转很小的角度重叠在一起,就能取最大值.

本帖遗 ...

还是用那个欧拉公式吗？$V_{n+1}-V_n=4+4E_n$，这个应该是对的，然后$E_{n+1}-E_n=4+2(V_{n+1}-V_n)$？这个有点疑问。

hbghlyj

abababa 发表于 2022-6-17 12:55 这个原理知道了，我开始以为不一定能构造出来。但是正m边形的结果不是那个吧，应该是$F_n=mn^2-mn+2$，其 ...

看来这里似乎由于语法的简写^[1]导致了一个歧义...

result.svg (2.33 KB, Downloads: 137)

2022-6-17 23:44 Upload

Click on the file to download the attachment

$n$条直线将一个圆分成的最多区域数(Circle Division by Lines) result-1.svg (1.72 KB, Downloads: 129)

2022-6-17 23:51 Upload

Click on the file to download the attachment

$n$条直线将一个正方形分成的最多区域数(Circle Division by Lines)

For n=1, 2, ..., this gives 2, 4, 7, 11, 16, 22, ... (OEIS A000124), which is the same number into which the plane, a circle, etc. can be divided.

正如Mathworld所写的,这两个是同一个问题.

不解释,而且其实封闭图形正方形,圆形分割也是这个答案.

知乎上的作者所指的也是,“$n$条直线分圆”和“$n$条直线分正方形”,是同一个问题.

但是正$m$边形的结果不是那个吧

这个是指“正$m$边形分平面”,是不同的问题.

hbghlyj

abababa 发表于 2022-6-17 12:55
这个原理知道了，我开始以为不一定能构造出来。但是正m边形的结果不是那个吧，应该是$F_n=mn^2-mn+2$，其 ...

对啊就是这个公式啊

abababa 发表于 2022-6-17 13:25
还是用那个欧拉公式吗？$V_{n+1}-V_n=4+4E_n$，这个应该是对的，然后$E_{n+1}-E_n=4+2(V_{n+1}-V_n)$？这 ...

对于$n$个正$m$边形划分平面,
第$n$个正$m$边形有$m$个顶点；添加第$n$个正$m$边形后,第$1,\dots,n-1$个正$m$边形的每条边上都多出2个交点,总共多出$2m(n-1)$个交点⇒$V_1=m,V_n=V_{n-1}+m+2m(n-1)⇒V_n=mn^2$
$n$个正$m$边形,每个正$m$边形有$m$条边,每条边被分割成$2n-1$条线段$⇒E_n=(2n-1)mn$
$F_n=2-V_n+E_n⇒F_n=mn^2-mn+2$

本帖遗留问题只剩9#那个凹四边形的区域数的计算

9#凹四边形的区域数怎么计算？
还是用那个欧拉公式。
对于$n$个凹四边形划分平面,
第$n$个凹四边形有4个顶点；添加第$n$个凹四边形后,第$1,\dots,n-1$个凹四边形的每条边上都多出4个交点,总共多出$16(n-1)$个交点⇒$V_1=4,V_n=V_{n-1}+4+16(n-1)⇒V_n=8n^2-4n$
$n$个凹四边形,每个凹四边形有4条边,每条边被分割成$4n-3$条线段$⇒E_n=(4n-3)4n$
$F_n=2-V_n+E_n⇒F_n=8n^2-8n+2$

所以说凹四边形的公式和正八边形的公式是一样的.

hbghlyj

把9#的$n=2$时的情况中的两个凹四边形其中一个对称一下,再稍微移动一下以避开三线共点,得到的图形果然有50个区域

drawing-2.svg (16.92 KB, Downloads: 97)

2022-6-18 03:05 Upload

Click on the file to download the attachment

abababa

hbghlyj 发表于 2022-6-18 00:47
对啊就是这个公式啊

正m边形的，是可以用最后那个旋转法构造出来，但对于n个圆分平面，就不能用那个方法构造了。凹多边形的我没什么兴趣。

hbghlyj

abababa 发表于 2022-6-18 03:05 正m边形的，是可以用最后那个旋转法构造出来，但对于n个圆分平面，就不能用那个方法构造了。凹多边形的我 ...

凹四边形的证明见15楼，也是用一样的方法