「ダイハード３」の水を４ガロン量りとる問題

こんにちは。東久留米市の学習塾塾長です。

昨日に比べて気温は下がりますが湿度が上がるようで、蒸し暑い日になるようです。近くの中学校では、今週末に運動会が開催されるところが多いですが、熱中症に気をつけて練習してください。

先週末に叔父の葬儀で熱海に行ってきましたが、戻ってきてＴＶを点けると「ダイハード３」を放映していました。以前に観た映画だったのですが、ビールを飲みながら観ていると、マクレーンとゼウスが公園に急行し、サイモンに出題された問題を解くシーンがありました。

その問題は、「３ガロンと５ガロンの容器を使って、４ガロンの水を量りとれ」というものです。

この問題の解法については、「理系への数学」（現在は現代数学）に斉藤浩先生がとても判りやすく解説されているので、それを紹介します。

そこでは、実行できる操作を３つに整理して、これらを基本操作と呼びます。

（１）ある容器に水道から水を満杯になるまで注ぐ
（２）ある容器の水を全部捨てる
（３）ある容器から別の容器に水を移す。その際、移動元の容器が空になるか、移動先の容器が満杯になるまで水を注ぎ続ける

次に、３ガロンの容器に入っている水の量をｘA、５ガロンの容器に入っている水の量をｘBとし、図１のように、ｘAを横軸、ｘBを縦軸としたグラフを描くと、ある時点での２つの容器にある水の量の状態を表す点は、図１の３×５の長方形の周上の格子点のいずれかになります。

▲図１．水の量の状態を表す点と基本操作による状態遷移

また、図１に描いた矢印は、基本操作（１）（２）（３）に対応します。

つまり、基本操作（１）は、上向きと右向きの矢印（赤色と青色）で、基本操作（２）は、下向きと左向きの矢印（赤色と青色）です。そして、基本操作（３）は、傾き－１の矢印（緑色）です。

また、矢印に従って状態が遷移する際には、矢印の終点まで移動し、途中で止まることはできません。

これで準備完了で、サイモンから与えられた問題は、図１の原点（３および５ガロンの容器が空の状態、ｘA＝ｘB＝０）から、矢印を通って、ｘB＝４の点に移動するルートを探す問題になりました。

そして、ｘB＝４の点に到達するルートは、図２、３のようになります。

▲図２．ｘB＝４に到達するルート（１）

▲図３．ｘB＝４に到達するルート（２）

例えば図２の場合、
<１>　５ガロン容器を水で一杯にする
<２>　５ガロン容器から３ガロン容器に３ガロンの水を移す
<３>　３ガロン容器の水を捨てる
<４>　５ガロン容器に残っていた２ガロンの水を３ガロン容器に移す
<５>　５ガロン容器を水で一杯にする
<６>　５ガロン容器から２ガロンの水が入っている３ガロン容器に１ガロンの水を移す⇒５ガロン容器に４ガロンの水が残り、これでお仕舞い
と６回の操作で４ガロンの水を量りとることができます。

図３については、興味があれば調べてみてください。