About
RSS

Bit Focus


划分问题与连续自然数幂和之通项公式

无限区间上 n 个不同的点可以把该区间分为多少段?

答案很明显, 当然是 (n + 1) 段啦. 另一个稍有难度的题目是, 无限平面上有n条直线, 问这些直线至多能把平面分成多少份? 在平面上画啊画就能归纳出解来的. 那么, 用 n 个平面, 最多能将无限三维空间划分成几个部分呢? 这个就略复杂了, 难道先建个 3D 模型, 然后归纳? 这个方法可行, 不过太浪漫和浪费了. 另外, 如果这个问题开始讨论维度更高的情形, 这种方法就行不通了. 那么, 问题来了:

使用 n 个 d 维 "*平整*" 的几何体, 来对无限 (d + 1) 维空间进行划分, 最多可以得到多少个部分?

不知道这个问题是否有官方名称了, 暂时称之为划分问题吧. 在这里, "平整" 指的是在该维度的空间中, 这些几何体的方程应该是线性的, 比如在 3 维空间中, 平面方程都可以表示为线性方程组 { $A_1 * x + B_1 * y = C_1$; $A_2 * x + B_2 * y = C_2$ }, 而在 1 维空间中的点就比较惨了, 就是 x = C, 不过还算是线性的. 其实大家只要有个基本的认识就行了, 不必这么刻板深究, 这篇文章中介绍的方法是没有严格证明的, 只是说说思路.

对能够画出来的各种维度进行一下归纳, 可以发现这样一个规律, 最开始开始的几次, 划分得到的空间区域是指数增长的:

  • 1 点分直线可以把直线分为 2 份
  • 1 直线分平面可以把平面分为 2 份, 2直线分平面可以把平面分为 4 份
  • 1 平面分空间可以把空间分为 2 份, 2平面分空间可以把空间分为 4 份, 3 平面分空间

可以把空间分为 8 份

这些规律可以*不完全归纳*假设为: n 个 d 维平整无限体分 (d + 1) 维无限体, 当 $n <= d$ 时, 可以分为 $2^n$ 份.

此外, 已知的结论有:

  • n 个点分直线至多将直线分为 (n + 1) 份;
  • n 条直线分平面至多将平面分为 ($(n^2) / 2 + n / 2 + 1$) 份;
  • n 个平面分空间至多将空间分为 ($(n^3) / 6 + 5 * n / 6 + 1$) 份;

所以再*不完全归纳*假设: n 个 d 维平整无限体分 (d + 1) 维无限体, 得到的份数 m 是 n 的一个幂多项式, 最高次项次数为 (d + 1).

由这些假设, 划分问题将可以用非常暴力的代数手段来解. n 个 d 维平整无限体分 (d + 1) 维无限体, 分得的空间数目 m 满足:

$ m = a_d * n^(d+1) + a_(d-1) * n^d + ... + a_0

这里 $a_x$ 是该多项式的系数.

现在代入 (n, m) = {(0, 1), (1, 2), ..., (d, $2^d$)}, 得到一个 (d + 1) 元一次方程, 这样就可以唯一地解出 $a_d$, $a_(d-1)$, ..., $a_0$ 这 (d + 1) 个系数.

类似的 (未经证明的) 方法同样可以用来连续自然数幂求和问题: 对于自然数 m 和给定的自然数 n, 求通项公式

$ a(m) = 0^n + 1^n + 2^n + ... + m^n

同样, 设出通项公式方程 (注: 没有常数项)

$ a(m) = a_k * m^(k+1) + a_(k-1) * m^k + ... + a_0 * m

然后根据没有化简的普通方程, 代入 m = { 1, ..., k }, 计算出前 k 个 a(m) (这个过程会很痛苦), 然后代入通项公式解方程 (唔, 这会更痛苦).

当然这只是另一个替代方案而已. Bernoulli 对自然数幂和公式的也做过研究, 他的方式是递推的, 运动量没有这个暴力方法大.

Permanent Link: /p/45 Load full text

Post tags:

 Algebra
 Algorithm
 Geometry


. Back to Bit Focus
NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
About this site