川渡りパズル

川を渡るオオカミ、ヤギ、キャベツ問題のアニメーション

川渡りパズルは、通常は最小限の移動で、ある川岸から別の川岸へ物を運ぶことを目的とするパズルの一種である。パズルの難しさは、同時に運べる物やその数、または安全に一緒に置いておける物やその数に制限があることから生じる場合がある。^{[ 1 ] [ 2 ]}設定は、例えば川を橋に置き換えるなど、見た目が変化する場合がある。^{[ 2 ]}最も古い川渡り問題は、伝統的にアルクインによって書かれたと言われている写本Propositiones ad Acuendos Juvenes (英語: Problems to sharpen the young )に見られる。この写本の最も古い写本は 9 世紀のものであり、オオカミ、ヤギ、キャベツ問題と宣教師と人食い人種問題を含む 3 つの川渡り問題が含まれている。^{[ 3 ]}

オオカミ、ヤギ、キャベツ問題

橋とトーチの問題

いくつかのパズルの解答をタイムラインとして表す

よく知られている川渡りパズルには次のようなものがあります。

• オオカミ、ヤギ、キャベツの問題。オオカミ、ヤギ、キャベツはボートで川を渡らなければなりませんが、ヤギとキャベツ、オオカミとヤギはどちらも一緒にいることはできません。このパズルは、キツネ、ガチョウ、豆の袋のパズルとしても表現できます。
• 宣教師と人食い人種問題。3人の宣教師と3人の人食い人種が川を渡らなければならない問題で、宣教師と人食い人種の両方がどちらかの岸に立っている場合、その岸にいる人食い人種の数が宣​​教師の数を上回ってはならないという制約がある。これは「嫉妬深い夫問題」とも呼ばれる。
• 橋と松明の問題。4人が夜、川にやって来ます。橋は狭く、一度に2人しか通れません。彼らは松明を1本持っていますが、夜なので橋を渡る時は松明を使わなければなりません。
• 大人一人分の体重しか支えられないボートで川を渡ろうとする男女の対立仮説。この問題は『若者の命題』にも登場するが、同じ体重の男性と女性、そしてそれぞれの体重が半分の子供二人が、大人一人分の体重しか支えられないボートで川を渡ろうとしている。^{[ 4 ]}

これらの問題はグラフ理論的手法^{[ 5 ] [ 6 ]} 、動的計画法^{[ 7 ]}、または整数計画法^{[ 4 ]}を用いて解析することができる。

グラフ理論的定式化

を無向グラフとし、その頂点集合は農夫が運ばなければならない品物を表し、辺集合は競合する品物のペアから構成されるものとする。例えば、頂点がガチョウと豆の袋を表す場合、ガチョウは豆の袋と同じ川岸に残すことはできないため、2つの頂点は接続されていることになる。2つの品物間の競合の性質は、それらを同じ川岸に残すことはできないという事実に影響を与えないため、辺は無向である点に注意されたい。問題の目的は、旅行が実行可能となるようなボートの最小サイズを決定することである。これは のアルクイン数として知られている。 ${\displaystyle G=(V,E)}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$ ${\displaystyle G}$

農夫がまず品物のサブセットを川に運び、残りの品物を岸に残すという、成功した川渡りを考えてみましょう。この旅が成功したため、岸に残された品物には衝突がないはずです。つまり、 において、の任意の2つの要素間にの辺は存在しません。これは、すべての辺が1つまたは両方の頂点を に持つことを意味します。つまり、 はの頂点被覆です。したがって、ボートのサイズはの最小頂点被覆のサイズ以上でなければなりません。これはの アルクイン数の下限を形成します。${\displaystyle V'}$ ${\displaystyle V\setminus V'}$ ${\displaystyle G}$ ${\displaystyle E}$ ${\displaystyle V\setminus V'}$ ${\displaystyle E}$ ${\displaystyle V'}$ ${\displaystyle V'}$ ${\displaystyle G}$ ${\displaystyle \tau (G)}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle {\rm {{アルクイン}(G)\geq \tau (G)}}}$

一方、ボートのサイズが であっても、航海を成功させることは可能です。これは、最小頂点被覆の要素が常にボートに乗っていることを条件とすることで実現できます。これらの要素の数は であり、ボートにもう1つのスペースが残ります。残りの要素には競合がないため、任意の順序で1つずつ川を渡ることができ、ボートの残りの1つのスペースを占めます。したがって、 は の上限を形成します。これらを組み合わせると 、つまりまたは となります。^{[ 1 ]}${\displaystyle \tau (G)+1}$ ${\displaystyle V'}$ ${\displaystyle \tau (G)}$ ${\displaystyle V\setminus V'}$ ${\displaystyle {\rm {{アルクイン}(G)\leq \tau (G)+1}}}$ ${\displaystyle {\rm {{アルクイン}(G)}}}$ ${\displaystyle \tau (G)\leq {\rm {{アルクイン}(G)\leq \tau (G)+1}}}$ ${\displaystyle {\rm {{アルクイン}(G)=\tau (G)}}}$ ${\displaystyle {\rm {{アルクイン}(G)=\tau (G)+1}}}$

Csorba、Hurkens、Woegingerは2008年に、またはのどちらが成り立つかを判断することがNP困難であることを証明した。^{[ 6 ]}最小頂点被覆問題はNP完全であるため、グラフのアルクイン数を計算することはNP困難である。しかし、グラフの特定のクラスについては、より強い結果が成り立つ。例えば、平面グラフの場合、2つの関係のどちらが成り立つかを判断することは多項式時間で行うことができる（ただし、またはのいずれかを判断することは依然としてNP困難である）。二部グラフの場合、、、はどちらも正確に多項式時間で計算できる。^{[ 6 ]}${\displaystyle {\rm {{アルクイン}(G)=\tau (G)}}}$ ${\displaystyle {\rm {{アルクイン}(G)=\tau (G)+1}}}$ ${\displaystyle G}$ ${\displaystyle {\rm {{アルクイン}(G)}}}$ ${\displaystyle \tau (G)}$ ${\displaystyle {\rm {{アルクイン}(G)}}}$ ${\displaystyle \tau (G)}$

参考文献

1. Numberphile (2018年1月5日).川の渡り方（とアルクイン数） - Numberphile . 2024年5月17日閲覧– YouTubeより。
2. Peterson, Ivars (2003)、「Tricky crossings」、Science News、164 (24)、2008年1月20日時点のオリジナルよりアーカイブ、2008年2月7日閲覧。。
3. p. 74、プレスマン、イアン；シングマスター、デイヴィッド（1989）、「「嫉妬深い夫たち」と「宣教師と人食い人種」", The Mathematical Gazette , 73 (464), The Mathematical Association: 73– 81, doi : 10.2307/3619658 , JSTOR  3619658。
4. ボルンドルファー、ラルフ;マーティン・グレッシェル; Löbel、Andreas (1995)、Alcuin の輸送問題と整数計画、プレプリント SC-95-27、Konrad-Zuse-Zentrum für Informationstechnik Berlin、2011 年 7 月 19 日のオリジナルからアーカイブ。
5. Schwartz, Benjamin L. (1961)、「「難しい交差」パズルの解析的手法」、Mathematics Magazine、34 (4): 187– 193、doi : 10.2307/2687980、JSTOR 2687980 。
6. コルバ、ペテル;ハルケンス、コル AJ; Woeginger、Gerhard J. (2008)、「グラフのアルクイン数」、アルゴリズム: ESA 2008、コンピューター サイエンスの講義ノート、vol. 5193、Springer-Verlag、pp.  320–331、doi : 10.1007/978-3-540-87744-8_27。
7. ベルマン、リチャード（1962）、「動的計画法と「難しい交差」パズル」、数学雑誌、35（1）、アメリカ数学会：27-29、doi：10.2307/2689096、JSTOR 2689096 。