这是用户在 2025-1-26 15:10 为 https://app.immersivetranslate.com/pdf-pro/71257d77-c20c-4f6d-9a3e-c10d8eb7df9a 保存的双语快照页面,由 沉浸式翻译 提供双语支持。了解如何保存?

  堆叠积木


是否可以像图 1 所示那样堆叠方块,使得底部方块的任何部分都不低于顶部方块?一般来说,顶部方块和底部方块之间可以有多大的水平距离?


图 1:一堆积木。

这是一个很好的数学问题。如果顶部块与底部块之间的距离有限,了解这个限制是什么将会很有趣。发现这个距离没有限制也会很有趣。


最终,这变成了一个问题,即顶部块的位置是收敛还是发散。

杰里森教授有八个积木;你认为他能用他所拥有的实现他的目标吗?

为了获得尽可能大的水平距离,从堆叠的顶部开始向下工作。最上面的块必须至少覆盖下面块的一半,否则它会掉落。将其滑动,使其右端位于下面块的中点。

接下来,将第二个方块尽可能向左滑动,而不影响塔的稳定。然后将下面的方块尽可能向左滑动,再滑动下面的那个,再滑动下面的那个,依此类推。


通过这种方式,杰里森教授仅用 7 个积木达成了他的目标。

如果我们有更多的积木,我们还能走多远?让我们来计算一下。

  计算


为了简化计算,假设每个块长 2 个单位。那么如果最上面的块的左端在位置 0,那么下面块的左端在位置 1。

一般来说,顶部 n n nn 块的质心必须始终位于支撑它们的块上方。

  • C 1 = C 1 = C_(1)=C_{1}= 成为顶部块的质心坐标 x x xx

  • C 2 = C 2 = C_(2)=C_{2}= 成为上面两个块的质心坐标 x x xx

  • 将下一个块的左端放在前一个块的质心下方。

问题:你怎么知道这是堆放它们的最佳方式?


答案:我不能一般性地回答这个问题,但我可以告诉你,如果我们从顶部开始构建,这是我们能做到的最好方法——我们使用计算机科学家所称的“贪心算法”,并在每一步尽可能地向前推进。

如果我们尝试从底部开始使用这个算法,它就行不通。我们会将第二个块的末端堆叠在第一个块的中点上,然后无法再获得任何超出这个距离。

似乎有可能存在某种比从顶部开始使用贪心算法更好的策略。实际上并没有,但我们今天不打算证明这一点。

根据我们的策略,我们需要知道 C N C N C_(N)C_{N} ,顶部 N N NN 块的质心的 x x xx 坐标,以便继续。


图 2:添加一个块。


如果顶部 N N NN 块的质心在 x = C N x = C N x=C_(N)x=C_{N} 线上,则 ( N + 1 ) s t ( N + 1 ) s t (N+1)^(st)(N+1)^{s t} 块的质心将具有 x x xx 坐标 C N + 1 C N + 1 C_(N)+1C_{N}+1 。这将质心向右移动;顶部 N + 1 N + 1 N+1N+1 块的新质心的 x x xx 坐标由堆叠的质心的加权平均值给出:
C N + 1 = N C N + 1 ( C N + 1 ) N + 1 = ( N + 1 ) C N + 1 N + 1 C N + 1 = C N + 1 N + 1 . C N + 1 = N C N + 1 C N + 1 N + 1 = ( N + 1 ) C N + 1 N + 1 C N + 1 = C N + 1 N + 1 . {:[C_(N+1)=(NC_(N)+1(C_(N)+1))/(N+1)],[=((N+1)C_(N)+1)/(N+1)],[C_(N+1)=C_(N)+(1)/(N+1).]:}\begin{aligned} C_{N+1} & =\frac{N C_{N}+1\left(C_{N}+1\right)}{N+1} \\ & =\frac{(N+1) C_{N}+1}{N+1} \\ C_{N+1} & =C_{N}+\frac{1}{N+1} . \end{aligned}

( N + 1 ) s t ( N + 1 ) s t (N+1)^(st)(N+1)^{s t} 块添加到堆栈中可以使堆栈从其基础延伸 1 N + 1 1 N + 1 (1)/(N+1)\frac{1}{N+1} 单位。
  所以
C 1 = 1 C 2 = 1 + 1 2 C 3 = 1 + 1 2 + 1 3 C 4 = 1 + 1 2 + 1 3 + 1 4 C 5 = 1 + 1 2 + 1 3 + 1 4 + 1 5 > 2 . C 1 = 1 C 2 = 1 + 1 2 C 3 = 1 + 1 2 + 1 3 C 4 = 1 + 1 2 + 1 3 + 1 4 C 5 = 1 + 1 2 + 1 3 + 1 4 + 1 5 > 2 . {:[C_(1)=1],[C_(2)=1+(1)/(2)],[C_(3)=1+(1)/(2)+(1)/(3)],[C_(4)=1+(1)/(2)+(1)/(3)+(1)/(4)],[C_(5)=1+(1)/(2)+(1)/(3)+(1)/(4)+(1)/(5) > 2.]:}\begin{aligned} C_{1} & =1 \\ C_{2} & =1+\frac{1}{2} \\ C_{3} & =1+\frac{1}{2}+\frac{1}{3} \\ C_{4} & =1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4} \\ C_{5} & =1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}>2 . \end{aligned}

至少需要 5 个区块才能将顶部区块延伸到基础之外。
C N = 1 + 1 2 + 1 3 + 1 4 + 1 5 + + 1 N C N = 1 + 1 2 + 1 3 + 1 4 + 1 5 + + 1 N C_(N)=1+(1)/(2)+(1)/(3)+(1)/(4)+(1)/(5)+cdots+(1)/(N)C_{N}=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\cdots+\frac{1}{N}

这个和 C N C N C_(N)C_{N} 与之前讲座中的 S N S N S_(N)S_{N} 是相同的:
C N = S N = n = 1 N 1 n C N = S N = n = 1 N 1 n C_(N)=S_(N)=sum_(n=1)^(N)(1)/(n)C_{N}=S_{N}=\sum_{n=1}^{N} \frac{1}{n}
  我们知道:
ln N < S N < ( ln N ) + 1 ln N < S N < ( ln N ) + 1 ln N < S_(N) < (ln N)+1\ln N<S_{N}<(\ln N)+1

由于 ln N ln N ln N\ln N N N NN 趋向于无穷大时 S N = C N S N = C N S_(N)=C_(N)S_{N}=C_{N} 也必须趋向于无穷大。如果我们有足够的积木,我们可以将我们的堆叠延伸到我们想要的任何远处。

在这个例子中, n = 1 N 1 n n = 1 N 1 n sum_(n=1)^(N)(1)/(n)\sum_{n=1}^{N} \frac{1}{n} 发散的事实意味着,只要我们有足够的积木,就可以将堆叠向左延伸到我们想要的任何远处。

另一方面,不等式 S N < ( ln N ) + 1 S N < ( ln N ) + 1 S_(N) < (ln N)+1S_{N}<(\ln N)+1 告诉我们,要将堆的顶部延伸得很远,需要很多块。

如果这堆积木跨越讲堂前面的两个实验桌,它的高度会有多高?一个实验桌长 6.5 块,或 13 个单位。两个桌子长 26 个单位。堆叠中将有 26 2 = 24 26 2 = 24 26-2=2426-2=24 个单位的悬垂。(我们减去 2,因为底部的积木没有悬垂,并且堆叠超出顶部积木的质心一个单位。)每块积木大约高 3 厘米。

如果 ln n = 24 ln n = 24 ln n=24\ln n=24 那么 n = e 24 n = e 24 n=e^(24)n=e^{24} 并且:
Height = 3 cm e 24 8 × 10 8 m  Height  = 3 cm e 24 8 × 10 8 m " Height "=3cm*e^(24)~~8xx10^(8)m\text { Height }=3 \mathrm{~cm} \cdot e^{24} \approx 8 \times 10^{8} \mathrm{~m}

那个高度大约是到月球距离的两倍。


如果你想让这个堆叠跨越这个房间( 30 ft 30 ft ∼30ft\sim 30 \mathrm{ft} .),它必须有 10 26 10 26 10^(26)10^{26} 米高。这大约是可观测宇宙的直径。

我们可以从这个实验中学到更多的东西 - 如果我们从侧面看这个堆叠,我们会发现它遵循 ln x ln x ln x\ln x 的图形。这项实验提供了一个具体的例子,说明函数 ln x ln x ln x\ln x 是多么缓慢地增长。

我们没有发现一个重要的数字来限制堆叠的范围,但我们确实发现这个范围是无限的——无穷大也是一个重要的数字。我们还发现了这个无限值的一个特性;那就是堆叠的扩展速度非常慢。


无限没有单一的值;有许多不同的无限序列。