Some Generalizations of the Bridge and Torch Problem

最もエキサイティングなパズルが、隠された宝探しや殺人事件の解決ではなく、日が昇る前に友人たちを暗く不安定な橋の向こう側へ渡らせることであるような世界を想像してみてください。これは組合せ最適化という数学の一分野の領域であり、「厳格なルールがあるとき、何かを行うための絶対的な最善の方法は何か？」と問いかけます。これは、ブロックの代わりに人々をタイムスロットに当てはめていく、究極のテトリスのゲームのようなものです。そして目標は、最短時間でレベルをクリアすることです。このゲームの古典的なバージョンは「橋とたいまつ問題（Bridge and Torch Problem）」として知られており、そのルールは一見すると非常に単純です。グループの人々は、たった一つの懐中電灯を持って夜に橋を渡らなければなりません。橋は狭く（一度に2人までしか渡れません）、誰かが渡るたびに懐中電灯を運ばなければならず、もし2人が一緒に渡る場合は、遅い方の人の速度に合わせて進みます。簡単そうに聞こえますが、最速のスケジュールを見つけ出すのは、タイミングと戦略の巧妙なダンスであり、多くの人々を悩ませてきました。

では、その同じパズルを取り上げて、難易度のダイヤルを上げてみたらどうなるでしょうか？ もし橋が3人を収容できたら？ あるいは、単一の橋の代わりに、クモの巣のように多くのスポークを持つハブ（中心点）があり、人々が同時に異なる目的地へ渡れるとしたら？ これこそが、Thang Pang ErnとGerard Saysonが論文で探求した内容です。彼らは、全員が1から$n$までの特定の渡る時間を設定した古典的な「2人用の橋」のパズルを取り上げ、単にそれを解くだけでなく、あらゆる人数に対して必要な最小時間を正確に予測する魔法の公式を見つけ出しました。さらに、彼らはその境界を押し広げ、3人を収容できる橋のルール、さらには星型の経路ネットワークについても解明しました。彼らは、答えは複雑になるものの、それらは単一の方程式として書き記すことができる、美しく繰り返されるパターンに従っていることを発見しました。

古典的な2人のダンス

まずは元のパズルから始めましょう。あなたは$n$人のグループを持っており、彼らの渡る時間は単に$1, 2, 3, \dots, n$です。時間は1の人はスプリンターであり、時間は$n$の人はのろまです。目標は、全員を川の左側から右側へ移動させることです。

著者たちは、この特定の構成において、最小時間$T(n)$を計算するための完璧な閉形式の公式が存在することを証明しました。それは単なる推測ではありません。彼らは問題を小さな塊に分解することで、それを導き出しました。彼らは、最適な戦略とは、まず最も速い2人（1と2）を先に渡らせ、そのうちの1人がたいまつを持って戻り、次に最も遅い2人を一緒に渡らせ、その後、もう一方の速い人が戻ってくるというものであることに気づきました。この「ブロック」の動きによって、2人の最も遅い人々が片付けられ、残りのグループに対してプロセスを繰り返す準備が整います。

これらのブロックのコストを足し合わせることで、彼らは$n$人の場合の総時間を見つけました：
$$T(n) = \frac{n^2}{4} + 3n - \frac{5 + (-1)^n - 1}{8}$$
この公式は、$n \ge 2$のすべての人数$n$に対して機能します。彼らはまた、生成される時間の数列（1, 2, 6, 11, ...）が数学の世界における既知のパターンであることを指摘しましたが、なぜこの特定の公式が機能するのかについて、新鮮で直接的な証明を提供しました。興味深いことに、彼らは、単に最も速い人が他の全員と一緒に何度も往復するという「標準的な」戦略が、常に最善であるとは限らないことを示しました。例えば、4人の場合、標準的な方法では、巧妙な「ブロック」法よりも時間がかかってしまいます。

3人を収容できる橋

次に、著者たちはこう問いかけました。「もし橋がもっと広かったら？」 彼らは、橋が一度に最大3人を収容できるが、依然として懐中電灯は1つしかない状況を想像しました。これはゲームを完全に変えてしまいます。3人の場合、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）における全く新しい数列を作り出しました。著者たちは、最適な戦略が、特定のサイクルで6人ずつのグループを動かすことで、問題を$n$人から$n-6$人へと、予測可能なコストを加えながら減少させていくものであることを示すことで、これを証明しました。彼らはまた、公式が数列の始まりに適合することを確認するために、小さな数（1から6まで）を総当たりでチェックしました。

彼らは4人を収容できる橋についても簡潔に触れましたが、パターンが煩雑になり、まだ単純な公式は見つけられなかったと認めています。彼らは公式が存在すると疑っていますが、それはより困難な作業です。

星型のネットワーク

最後に、この論文は単一の橋から大きく離れた飛躍を遂げます。中心となるハブ（駅のようなもの）があり、そこからさまざまな目的地（葉）へと続く多くの道路（スポーク）がある状況を想像してください。これは「スターグラフ」と呼ばれます。このバージョンでは、ルールが少し異なります。1つの「ステップ」において、誰も同じ道を使わず、かつ一人が二箇所に同時に存在しない限り、異なる道を通って人々を同時に送り出すことができます。そのステップの時間は、そのステップで動いている最も遅い人の時間によって決定されます。

ここでのルールは、あなたが持つ懐中電いない灯と道路の数に大きく依存します。もし、全員を一度の大きな放出で送り出すのに十分な数の懐中電灯と道路があれば、時間は単に最も遅い人の時間（$n$）になります。しかし、制限がある場合、時間はだいたい$n^2$のように増加します。彼らは下限の公式を導き出しました：
$$T(n, k, t) \ge sn - ms(s-1)$$
ここで、$m$は道路の数または懐中電灯の数の小さい方であり、$s$は全員を送り出すのに必要な「ラウンド」の数です。

このセクションの最もクールな部分の一つは、それが純粋数学とどのように結びついているかです。彼らがこのスターグラフ問題によって生成される数値を調べたとき、彼らは「床関数」（単に小数点以下を切り捨てるという意味）を含む有名な数学的恒等式を再現していることに気づきました。例えば、特定の人数と道路の数についてパズルを解くことで、彼らは床関数の和に関する既知の恒等式を「再発見」し、楽しいスケジューリングパズルがいかに深い数パターンの真実を明らかにするかを示しました。

要するに、この論文は古典的な謎を取り上げ、精密な公式で解決し、より広い橋へと拡張し、さらに多経路のネットワークへと回転させ、その過程で隠された数学的な美しさを発見しています。それは、単純な橋渡しのゲームの中にさえ、発見されるのを待っている戦略と構造の層が存在することを示しています。