当サイトを閲覧いただきありがとうございます。 本記事は面接パズルの帝王「橋とたいまつの問題」について解説します。
夜、4人が古い吊り橋の前に立っています。橋は暗くて危険なため、渡るにはたいまつが必須ですが、たいまつは1本だけ。橋は同時に2人までしか渡れません。4人の足の速さはバラバラで、渡るのにそれぞれ1分・2分・5分・10分かかり、2人で渡ると遅い方に合わせることになります。さて、全員が橋を渡り切るまでの最短時間は何分でしょうか。ほとんどの人が19分と答えますが、正解は17分。その2分差に、段取りの発想を根本から変える一手が隠れています。
橋とたいまつの問題とは
橋とたいまつの問題（英語では bridge and torch problem）とは、共有資源（たいまつ）の受け渡しを含む移動の段取りを最適化するパズルです。ルールを整理しておきます。
・4人が橋の同じ側にいて、全員が反対側へ渡りたい ・橋を渡るにはたいまつが必要。たいまつは1本しかない ・橋は一度に2人まで。2人で渡るときの所要時間は遅い方の時間 ・4人の所要時間は1分・2分・5分・10分。たいまつは誰かが持って歩いて運ぶ（投げ渡し禁止）
このパズルは1980年代のパズル書に載ったのが知られる限り最も古い活字とされ、1990年代にはマイクロソフトの採用面接で出題される問題として世界的に有名になりました。当時の面接では「17分で渡れることが分かっている」とヒント付きで出題され、多くの候補者が「19分までしか縮まない、問題が間違っているのでは」と苦しんだと言われています。ロックバンドU2のメンバー4人がコンサート開始前の17分で橋を渡る、という設定のコピーがインターネットで拡散したことでも知られています。
直感の答えは「最速の1分が全員を送迎する」19分
まず、ほぼ全員が最初に思いつく作戦を見てみます。たいまつを持って往復する役は、当然いちばん速い1分の人にやらせるべきだ、という発想です。
①1分と10分が渡る（10分） ②1分がたいまつを持って戻る（1分） ③1分と5分が渡る（5分） ④1分が戻る（1分） ⑤1分と2分が渡る（2分）
合計は19分。最速の人をシャトル役に固定し、遅い人を1人ずつ運ぶ。どこにも無駄がないように見えます。実際、この作戦の中では1秒も削れません。
しかし合計の内訳を見ると、弱点が浮かびます。10分と5分という2つの大きな数字が、両方ともまるごと合計に乗っているのです。遅い人を別々に運ぶ限り、この2つの足し算からは逃げられません。
正解は「最も遅い2人を一緒に渡らせる」17分
正解の手順はこうです。
①1分と2分が渡る（2分） ②1分がたいまつを持って戻る（1分） ③10分と5分が渡る（10分） ④向こう岸で待っていた2分が、たいまつを持って戻る（2分） ⑤1分と2分が渡る（2分）
合計は2＋1＋10＋2＋2で17分です。
鍵は③にあります。最も遅い10分と5分を同じ便に乗せることで、5分は10分の陰に完全に隠れ、合計に一切顔を出さなくなります。遅い2人を別送すれば10＋5で15分かかるところが、同送なら10分だけ。ここで5分を丸ごと節約できるのです。
ただし、この作戦には仕掛けの準備が要ります。遅い2人が渡り終えたあと、たいまつを持ち帰る役が向こう岸にいなければなりません。遅い2人に持ち帰らせては元も子もないからです。だから①で速い2人を先に向こう岸へ送り、帰りの運転手（2分）をあらかじめ配置しておく。①と②は一見無駄な往復に見えて、実は③の大輸送のための布石だったわけです。この「後の一手のために先に人を配る」組み立ては、川渡り問題の「ヤギを連れて戻る」と並ぶ、段取りパズルの名手筋だと思います。
遅い2人を組ませるべきかは足し算で決まる
では、遅い2人を組ませる作戦は常に正しいのでしょうか。実は違います。4人の所要時間を速い順にa・b・c・dとすると、2つの作戦の合計は次の通りです。
・最遅ペア方式：a＋3b＋d ・最速シャトル方式：2a＋b＋c＋d
引き算をすると、最遅ペア方式が勝つ条件は「2b が a＋c より小さいこと」だと分かります。つまり、2番目に速い人が十分速いなら帰りの運転手を任せられるのでペア方式が得になり、2番目が遅いならシャトル方式のままが良い。1・2・5・10分では2bが4、a＋cが6なのでペア方式の勝ちです。逆にたとえば1・4・5・10分なら2bが8、a＋cが6となり、最速シャトル方式（合計21分）の方が最遅ペア方式（合計23分）に勝ちます。
どちらの作戦が最適かが、パラメータ次第でひっくり返る。これがこのパズルのもう一段深い味わいです。「この手筋は常に正しい」と丸暗記した瞬間に足をすくわれる作りになっていて、面接の題材として愛された理由もよく分かります。なお、人数が増えた場合も「速い2人を運転手にして、遅い2人ずつをまとめて送り込む」手筋の繰り返しが基本形になることが知られており、一般の場合の完全な解析は2002年に数学者ローテの論文で与えられています。
ボトルネックは並べて隠せ
このパズルの教訓は、実務の言葉に翻訳すると「遅い処理同士は重ねて、速い処理の陰に隠すな」となります。
たとえば、時間のかかる2つの処理を含む一連の作業があるとします。サーバーの再起動とデータの移行、大型機材の搬入と電源工事、時間のかかる承認と長納期部品の発注。これらを順番にこなせば所要時間は足し算ですが、同時に走らせれば遅い方だけで済みます。プロジェクト管理で言うクリティカルパスの短縮であり、料理で言えば煮込みの間に下ごしらえを済ませる、あの発想です。
見落としがちなのは、並走を実現するための「布石の一手」に先行投資が要る点です。17分の解では、①②の3分がその投資でした。目先の3分だけ見れば無駄な往復ですが、それが後の5分の節約を可能にします。一手ごとの効率だけを評価すると、布石の一手が「無駄」として却下され、全体最適に届かない。川渡り問題と同じ教訓が、時間の最適化という違う土俵でも顔を出すわけです。
ソフトウェア開発なら、実行に時間のかかるテスト群を思い浮かべてください。遅いテスト2本を別々の待ち時間で流せば両方の時間を支払いますが、並列に流せば遅い方だけで済みます。そのために実行環境をもう1面用意する手間が「布石の3分」に当たります。引っ越しの段取りで、時間のかかる回線工事と大型家具の搬入を同じ日に重ねるのも同じ発想です。「一番遅いものは何か、それは何と重ねられるか」と問う癖をつけると、いろいろな待ち時間が縮み始めます。
最短の証明と、人数を増やした場合
なぜ最速の人が全員を送るのが最適ではないのですか？
最速シャトル方式の弱点は、遅い人たちの所要時間が全員分そのまま合計に乗ることです。1分の人の往復は確かに最安ですが、10分と5分を別々の便にした時点で15分の支払いが確定します。最遅ペア方式は、帰りの運転手代として2分の人の便を余分に使う代わりに、5分を丸ごと消します。「運び役のコスト」と「遅い人を別送するコスト」のどちらが重いかという比較であり、答えは数字次第で変わります。
16分では渡れないのですか？
渡れません。まず10分の人が渡る便で最低10分かかります。さらに、たいまつを戻すために少なくとも2回の帰り便が必要で、どんなに速くても1分と2分（帰り役を同じ人にしても1分＋1分）。加えて最後の便以外にもう1本の行き便が要ります。すべての必要な便を最小の組み合わせで数え上げると、17分を下回る割り当てが存在しないことが確かめられます。パズルの答えとしては、17分の手順の存在と、16分以下の不可能性の両方がそろって初めて「最短17分」と言い切れる点も、良い教材だと思います。
5人以上になったらどう考えればよいですか？
基本方針は同じで、「速い2人を行き帰りの運転手に固定し、残りを遅い順に2人ずつペアで送り込む」形と、最速シャトルとの混合が候補になります。1ラウンドごとに、最遅ペアをまとめて送るコスト（a＋2b＋遅い方）とシャトルで2人送るコストを比べて安い方を選ぶ、という繰り返しで最適解が組み立てられます。人数が増えても「遅い者同士を重ねる」原理は変わらないところが、この手筋の美しさです。
関連する論理クイズ・パズル
「後退に見える布石」の元祖「川渡り問題」、再帰の分解で最短手数を導く「ハノイの塔」、1回の操作の情報量から手数の下限を数える「12枚のコインと天秤」の記事です。
まとめ
本記事は「橋とたいまつの問題」について解説しました。如何だったでしょうか。
19分の作戦は、一手一手がすべて合理的なのに全体では負けています。17分の作戦は、無駄に見える往復を含むのに全体では勝っています。この対比が示すのは、部分の効率の積み上げは全体の最適を保証しないという、最適化の世界の基本原理です。
そして勝敗を分けた一手は、「最も遅い2人を同じ便に乗せて、遅さを重ねて隠す」でした。私も段取りを組むときは、まず一番遅い作業を書き出して、それに何を重ねられるかから考えるようになりました。遅いもの同士を並走させられないかを先に疑う。この2分差の削り方は、案外いろいろな仕事に応用が利きます。
論理クイズ・確率パズルの一覧に戻りたい方は以下のリンクからどうぞ。
それでは次の記事も閲覧いただけると幸いです。
📚 シリーズ：論理クイズ・確率パズル（8/11）
