水をかけるパズル

水差し問題（水差し問題、デカント問題、^{[1] [2]} 測定パズル、またはダイ・ハード・ウィズ・ア・ヴェンジェンス・パズルとも呼ばれる）は、既知の整数容量（リットルやガロンなどの液体の単位で）の水差しの有限のコレクションを含むパズルの一種です。最初、各水差しには既知の整数体積の液体が入っており、必ずしもその容量に等しいとは限りません。

このタイプのパズルは、目標状態に到達するために、1つの水差しから別の水差しに水を注ぐステップ（片方の水差しが空になるか、もう片方の水差しがいっぱいになるまで）が何回必要かを問うもので、目標状態は、いくつかの水差しまたは複数の水差しに入っている必要がある液体の量で指定されます。^[3]

ベズーの恒等式によれば、このようなパズルは、目的の容積が水差しのすべての整数容積の 最大公約数の倍数である場合にのみ解が存在します。

これらのパズルの一部として述べられている一般的な仮定は、パズル内の水差しは不規則な形をしており、マークが付いていないため、水差しが完全に満たされない水の量を正確に測定することは不可能であるということです。これらの問題のその他の仮定には、水がこぼれることはないこと、および元の水差しから目的の水差しに水を注ぐ各ステップは、元の水差しが空になるか目的の水差しがいっぱいになるかのどちらかが先に起こった時点で停止することが含まれます。

この種の標準的なパズルは、容量が 8、5、3 リットルの水差し 3 つで解くことができます。これらの水差しは、最初は 8、0、0 リットルで満たされています。目標状態では、4、4、0 リットルで満たされているはずです。このパズルは、次の一連の状態 (3 つの水差しの 3 つの水量を括弧で囲んだ 3 つ組として表される) を経て、7 つのステップで解くことができます。

[8,0,0] → [3,5,0] → [3,2,3] → [6,2,0] → [6,0,2] → [1,5,2] → [1 ,4,3]→[4,4,0]。

カウリー (1926) は、この特定のパズルは「中世にまで遡る」と記しており、バシェの 17 世紀の数学の教科書に登場していることを指摘しています。

ルールでは、直交グリッドの境界（つまり、各水差しの最大容量）でのみ停止/回転が許可されているため、元に戻せるアクション（1 ステップで元に戻せるアクション）は次のものだけです。

• 満杯の水差しから任意の水差しに水を移す
• 任意の水差しから空の水差しに水を移す

1 つのステップで元に戻すことができない唯一の不可逆的なアクションは次のとおりです。

• 半分満たされた水差しから半分満たされた別の水差しに水を移す

可逆的な動作のみに限定することで、望ましい結果から問題の解決策を構築できます。点 [4,4,0] からは、8 リットルの水差しから 3 リットルを空の 3 リットルの水差し [1,4,3] に移すことと、5 リットルの水差しから 3 リットルを空の 3 リットルの水差し [4,1,3] に移すことの 2 つの可逆的な動作しかありません。したがって、この問題には 2 つの解決策しかありません。

[4,4,0] ↔ [1,4,3] ↔ [1,5,2] ↔ [6,0,2] ↔ [6,2,0] ↔ [3,2,3] ↔ [3] ,5,0] ↔ [8,0,0]

[4,4,0] ↔ [4,1,3] ↔ [7,1,0] ↔ [7,0,1] ↔ [2,5,1] ↔ [2,3,3] ↔ [5 ,3,0] ↔ [5,​​0,3] ↔ [8,0,0]

ルールは、蛇口（水が無限に流れる水差し）とシンク（水を無制限に受けられる排水口）を追加することで定式化されることがある。蛇口から水差しの縁まで水を満たすか、水差しの中身をすべて排水口に流すかは、問題を解く際の1ステップとしてカウントされる。このバージョンのパズルは、1995年の映画「ダイ・ハード4 」のワンシーンで取り上げられた。^[4]このバリエーションには、ビリヤード型の重心プロット（または数学的ビリヤード）を使用して得られる最適解がある。^[5]

このグラフは、3 リットルと 5 リットルの水差しを使用して 4 リットルを得る 2 つの方法と、傾きが -1 の対角線を持つ直交座標グリッド上の水源とシンクを示しています (これらの対角線は、一方の水差しからもう一方の水差しに水を注ぐことを表します)。x 軸とy軸は、それぞれ 5 リットルの水差しと 3 リットルの水差しの量を表します。(0, 0) から始めて、境界線上でのみ回転しながら、グリッドを線分に沿って移動し、5 リットルの水差しに 4 リットル入っていることを示す黒い線に到達します。実線は水差し間の注ぎ、破線は水差しへの水差しの充填、点線は水差しの空を示します。 ${\displaystyle x+y=const.}$

いずれかの解を連結し、4 L ラインを横断し、他の解の逆を行うと (0, 0) に戻り、サイクル グラフが生成されます。水差しの体積が互いに素である場合に限り、すべての境界点が訪問され、体積の合計までの任意の整数値を測定するアルゴリズムが提供されます。

前のセクションで示したように、可逆的なアクションのみを使用して、目的の結果から問題の解決策を構築できます (満杯の水差しをシンクに空にすることと、蛇口から空の水差しに水を入れることはどちらも可逆的です)。3 リットルと 5 リットルの水差しを使用して 4 リットルを得るには、ポイント (4, 0) に到達する必要があります。ポイント (4, 0) からは、蛇口から空の 3 リットルの水差しを満杯にすること (4,3) と、5 リットルの水差しから 3 リットルの水差しに 1 リットルの水を移すこと (1,3) の 2 つの可逆的なアクションしかありません。したがって、問題には 2 つの解決策しかありません。

(4, 0) ↔ (4, 3) ↔ (5, 2) ↔ (0, 2) ↔ (2, 0) ↔ (2, 3) ↔ (5, 0) ↔ (0, 0)

(4, 0) ↔ (1, 3) ↔ (1, 0) ↔ (0, 1) ↔ (5, 1) ↔ (3, 3) ↔ (3, 0) ↔ (0, 3) ↔ (0 、0)

サイクル グラフは、可逆的なアクションによって接続された順序付きペアで表すことができます。

(0, 0) ↔ (5, 0) ↔ (2, 3) ↔ (2, 0) ↔ (0, 2) ↔ (5, 2) ↔ (4, 3) ↔ (4, 0) ↔ (1) 、3) ↔ (1, 0) ↔ (0, 1) ↔ (5, 1) ↔ (3, 3) ↔ (3, 0) ↔ (0, 3) ↔ (0, 0)

これには、3 リットルの水差しと 5 リットルの水差しで到達可能なすべての状態が含まれています。たとえば、(1, 2) の状態は、(0, 0) の初期状態から到達することは不可能です。これは、(1, 2) では両方の水差しが部分的に満たされており、この状態から元に戻す操作は不可能であるためです。

もう 1 つのバリエーション^[6]は、一方の水差しに最初から既知の量の水が入っている場合です。その場合、達成可能な量は、既存の既知の量から 2 つの容器の最大公約数の倍数か、ゼロからのいずれかになります。たとえば、8 リットル入る一方の水差しが空で、12 リットル入るもう一方の水差しに最初から 9 リットルの水が入っている場合、水源 (蛇口) と排水口 (シンク) があれば、これら 2 つの水差しは 9 リットル、5 リットル、1 リットルのほか、12 リットル、8 リットル、4 リットル、0 リットルの量を測定できます。5 リットルの最も単純な解は (9,0) → (9,8) → (12,5) です。4 リットルの最も単純な解は (9,0) → (12,0) → (4,8) です。これらの解は、水平方向と垂直方向の両方に 4 リットル間隔で配置された対角線 (これらの対角線上では傾きが -1 である) を持つ直交座標グリッド内の赤と青の矢印によって視覚化できます。 ${\displaystyle x+y=const.}$

再び、可逆的な動作のみに限定すると、目的のポイント (5,0) からは、12 リットルの水差しから 8 リットルの水差しに 5 リットルの水を移す (0,5) か、空の 8 リットルの水差しに蛇口から水を満杯にする (5,8) という 2 つの可逆的な動作しかありません。したがって、この問題の解決方法は 2 つしかありません。

(5, 0) ↔ (0, 5) ↔ (12, 5) ↔ (9, 8) ↔ (9, 0)

(5, 0) ↔ (5, 8) ↔ (12, 1) ↔ (0, 1) ↔ (1, 0) ↔ (1, 8) ↔ (9, 0)

4 リットルの問題では、 であるため、解決の開始時に 1 つの不可逆なアクションが必要です。それは、12 リットルの水差しから 9 リットルの水を全部シンク (0,0) に注ぐか、蛇口 (12,0) から 12 リットルまで満たすことです。その後、前と同じように逆方向にソリューションを構築できます。 ${\displaystyle 4\equiv 0\!\mod \!4}$

(4, 0) ↔ (4, 8) ↔ (12, 0) ← (9, 0)

(4, 0) ↔ (0, 4) ↔ (12, 4) ↔ (8, 8) ↔ (8, 0) ↔ (0, 8) ↔ (0, 0) ← (9, 0)

水差しの数が3つであれば、3つの整数の合計がすべてのステップを通じて同じままであるため、各ステップ後の充填状態は重心座標の図で表すことができます。 ^[7]結果として、ステップは三角格子上の（クリップされた）座標系でのビリヤードの動きとして視覚化できます。

右側の重心プロットは、8、5、3 L パズルの 2 つの解を示しています。黄色の領域は、水差しで達成可能な組み合わせを示しています。正方形から始めて、実線の赤と破線の青のパスは、注ぎ込み可能な遷移を示しています。頂点が点線の黒の三角形に着くと、4 L が測定されます。ダイヤモンドにもう一度注ぐと、8 L と 5 L の水差しのそれぞれに 4 L が得られます。

青いパスは、蛇口と排水口のある 2 つの水差しのパズルのパスよりも 1 ステップ短くなっています。これは、2 つの水差しのバリエーションにはない 4 つの L を蓄積できる 8 L の水差しがあるためです。

• ロープ燃焼パズル、測定値の組み合わせを伴う別の種類のパズル
• アインステリング効果

• カウリー、エリザベス B. (1926)。「線形ディオファントス方程式に関する注釈」。質問と議論。アメリカ数学月刊誌。33 ( 7): 379–381。doi :10.2307/2298647。JSTOR 2298647。MR  1520987  。
• Tweedie, MCK (1939)。 「タルタグリアの測定パズルを解くグラフィカルな方法」。The Mathematical Gazette。第 23 巻、第 255 号。pp. 278–282。JSTOR  3606420。
• サクセナ、日本 (1968)。 「確率的最適ルーティング」。Unternehmensforschung。12 (1): 173–177。土井：10.1007/BF01918326。S2CID  10064660。
• アトウッド、マイケルE .; ポルソン、ピーター G. (1976)。「水差しの問題に対するプロセスモデル」。認知心理学。8 ( 2): 191–216。doi :10.1016/0010-0285(76)90023-2。S2CID 54388726  。
• Rem, Martin; Choo, Young il ( 1982)。「3つの容器の問題に対する線形出力複雑度の固定空間プログラム」。コンピュータプログラミングの科学。2 (2): 133–141。doi : 10.1016/0167-6423(82)90011-9。
• Thomas, Glanffrwd P. (1995)。 「水差し問題: 人工知能と数学的観点からの解決法」。Mathematics in School。第 24 巻、第 2 号。pp. 34–37。JSTOR  30215221。
• Murray-Lasso, MA (2003)。「数学パズル、問題解決の指導における強力なアイデア、アルゴリズム、コンピュータ」。応用研究技術ジャーナル。第 1 巻、第 3 号。215 ～ 234 ページ。
• ラルチェフ、ズドラフコ・ヴトフ。ヴァルバノバ、マルガリータ・ジェノバ。ヴトヴァ、イリルナ・ズドラフコワ (2009)。 「液体注入問題を解決するパールマンの幾何学的な方法」。
• Goetschalckx, Marc (2011)。「ネットワークを介した単一フロールーティング」。サプライチェーンエンジニアリング。オペレーションズリサーチ＆マネジメントサイエンスの国際シリーズ。第161巻。pp. 155–180。doi : 10.1007 / 978-1-4419-6512-7_6。ISBN 978-1-4419-6511-0。