Some Generalizations of the Bridge and Torch Problem

想象这样一个世界：最令人兴奋的谜题不再是寻找隐藏的宝藏或破解谋杀案，而是如何在太阳升起之前，让一群朋友穿过一座黑暗且摇摇欲坠的桥。这就是组合优化（combinatorial optimization）的领域，这是一个研究“在拥有严格规则时，完成某事的绝对最佳方式”的数学分支。把它想象成终极版的俄罗斯方块，只不过你放入其中的不是方块，而是将人们填入时间槽中，而目标是在最短时间内完成关卡。这个游戏的经典版本被称为“过桥与火炬问题”（Bridge and Torch Problem），它以其看似简单实则深奥的规则而闻名：一群人必须在夜晚穿过一座桥，且只能携带一只手电筒。桥很窄（一次只能容纳两人），每次有人过桥时必须携带手电筒，而且如果两人同行，他们的速度取决于其中较慢的那个人。这听起来很简单，但寻找最快的时间表是一场关于时机与策略的复杂舞蹈，曾让许多人感到困惑。

现在，想象一下将那个同样的谜题进行升级。如果桥可以容纳三个人呢？或者，如果你拥有的不是单座桥，而是一个像蜘蛛网一样具有多个辐条的中心枢纽，人们可以同时前往不同的目的地呢？这正是 Thang Pang Ern 和 Gerard Sayson 在他们的论文中所探讨的内容。他们拿出了经典的“两人过桥”谜题——其中每个人的过桥时间分别为 $1$到$n$——并且他们不仅解决了它，还发现了一个神奇的公式，可以预测任何人数下的确切最小时间。随后，他们进一步拓展了边界，推导出了容纳三人的桥梁规则，甚至是星形网络路径的规则。他们发现，尽管答案变得复杂，但它们遵循着美丽的、重复的模式，可以用一个单一的方程来表达。

经典的两人之舞

让我们从原始谜题开始。你有 $n$ 个人，他们的过桥时间分别是 $1, 2, 3, \dots, n$。时间为 1 的人是短跑健将，而时间为 $n$ 的人则是慢郎中。目标是将所有人从河流左侧转移到右侧。

作者证明了对于这种特定的设置，存在一个完美的闭式公式来计算最小时间 $T(n)$。这不仅仅是一个猜测；他们是通过将问题分解成更小的块来推导出来的。他们意识到，最佳策略是先派两个最快的人（1 和 2）过去，让其中一人带着火炬返回，再让两个最慢的人一起过去，然后让另一个快的人返回。这个“移动块”清除了两个最慢的人，并让系统准备好对剩余群体重复此过程。

通过累加这些移动块的成本，他们发现 $n$ 个人的总时间为：
$$T(n) = \frac{n^2}{4} + 3n - \frac{5 + (-1)^n - 1}{8}$$
该公式适用于每一个大于或等于 2 的人数 $n$。他们还指出，生成的序列（1, 2, 6, 11, ...）是数学界中一个已知的模式，但他们为为什么这个特定公式有效提供了全新的直接证明。有趣的是，他们表明仅仅让最快的人带着每个人来回往返的“标准”策略并不总是最好的。例如，对于 4 个人，标准方法比聪明的“移动块”方法耗时更长。

能容纳三人的桥

接下来，作者问道：“如果桥更宽了呢？”他们设想了一座一次最多可容纳 3 人的桥，但仍然只有一只手电筒。这完全改变了游戏规则。有了三个人，你可以派一个三人组过去，但你仍然需要有人把光带回来。

他们发现，对于这个“容量为 3”的版本，最优时间 $T_3(n)$ 遵循一种不同且更复杂的节奏。该公式涉及一个二次曲线（类似于 $n^2/6$）和一些包含余弦函数和 $(-1)^n$ 的波动项。具体来说，对于 $n \ge 7$，时间为：
$$T_3(n) = \frac{n^2}{6} + 2n - \frac{181}{36} + \frac{(-1)^n}{4} - \frac{2}{9} \cos\left(\frac{2n\pi}{3}\right)$$
这个公式如此独特，以至于它创造了一个全新的整数数列（A392834）。作者通过证明最佳策略涉及以特定的循环方式每六个人一组地移动，从而将问题从 $n$ 个人减少到 $n-6$ 个人，并伴随可预测的成本增加，从而证明了这一点。他们还通过暴力破解检查了较小的数字（如 1 到 6），以确保公式符合序列的起始部分。

他们简要观察了一个容纳 4 人的桥，但他们承认模式变得混乱了，目前还无法找到一个简单的公式。他们怀疑存在一个公式，但寻找它要困难得多。

星形网络

最后，论文进行了一次向单桥之外的巨大飞跃。想象一个中心枢纽（类似于火车站）带有许多道路（辐条）通往不同的目的地（叶节点）。这被称为“星形图”。在这个版本中，你拥有 $n$ 个人， $k$ 条道路，以及 $t$ 个手电筒。

这里的规则略有不同：在一个“步骤”中，你可以向不同的道路发送人员，只要没有人使用相同的道路，且没有人在两个地方同时出现。该步骤的时间由该步骤中移动的最慢的人决定。

作者发现，最小时间在很大程度上取决于你拥有的手电筒和道路数量。如果你有足够的灯和路，可以在一次大爆发中送出所有人，那么时间就是最慢的人的时间（$n$）。但如果你受到限制，时间会大致呈 $n^2$ 增长。他们推导出了一个下界公式：
$$T(n, k, t) \ge sn - ms(s-1)$$
其中 $m$ 是道路数量或手电筒数量中的较小值，$s$ 是将所有人送出所需的“轮数”。

这一部分的精彩之处在于它如何与纯数学联系起来。当他们观察星形图问题生成的数字时，他们意识到自己正在重现涉及“取整函数”（floor function，即向下取整到最近的整数）的著名数学恒等式。例如，通过解决特定人数和道路数的谜题，他们“重新发现”了一个关于取整函数之和的已知恒等式，展示了这样一个有趣的调度谜题如何揭示数字模式中的深刻真理。

简而言之，这篇论文将一个经典的谜题进行了拆解，用精确的公式解决了它，将其扩展到更宽的桥梁，然后将其旋转成一个多路径网络，同时在过程中揭示了隐藏的数学之美。它表明，即使是在一个简单的过桥游戏中，也蕴含着等待被发现的策略层级与结构。