猿とココナッツ

猿とココナッツは、砂漠の島で5人の船乗りと猿がココナッツの山を分けるという短編小説に由来する、ディオファントス解析の分野における数学パズルです。問題は、元の山にあるココナッツの数を求めることです（端数のココナッツは認められません）。この問題は、パズルを解くのが未熟な人にとってはとんでもなく難しいことで有名ですが、適切な数学的アプローチをとれば、解くのは簡単です。この問題は、娯楽数学のコレクションの定番となっています。

この問題は次のように表現できます。

5 人の男が所有するココナッツの山があります。1 人の男が山を 5 つの均等な山に分け、残ったココナッツ 1 つを通りかかった猿に渡し、自分の取り分を取ります。次に、2 人目の男が残りの山を 5 つに分け、自分の取り分を取ります。3 人目、4 人目、5 人目も同様に繰り返し、山を 5 で割ったときにココナッツが 1 つ余っているのを見つけて、それを猿に渡します。最後に、グループは残りのココナッツを 5 つの均等な山に分けます。今度はココナッツは 1 つも残りません。

元々の山にはココナッツがいくつありましたか?

サルとココナッツは、離散的に割り切れる量の再帰的割り算または分数化 (余りありまたは余りなし) と、場合によっては余りのあるいくつかの均等な部分への最終的な割り算として構成された整数解を必要とするパズル問題のクラスの最もよく知られた代表例です。この問題は非常によく知られているため、クラス全体が広く「サルとココナッツ型の問題」と呼ばれることがよくありますが、そのほとんどはこの問題と密接に関連していません。

別の例: 「私は整数ポンドのセメントを持っています。その数はわかりませんが、9 分の 1 と 11 分の 1 を加えた後、整数ポンドずつ 3 つの袋に分けられました。私のセメントは何ポンドありましたか?」

問題では、初期量または終端量のいずれかが求められます。明示的または暗黙的に示されるのは、解となり得る最小の正数です。このような問題には、初期数と終端数の 2 つの未知数がありますが、それらの関係を表す式の代数的簡約である方程式は 1 つだけです。このクラスに共通するのは、結果として得られる方程式の性質で、2 つの未知数を持つ線形ディオファントス方程式です。このクラスのメンバーのほとんどは決定的ですが、そうでないものもあります (サルとココナッツは後者の 1 つです)。このような方程式を解くのに、一般的な代数的方法は役に立ちません。

こうした問題の起源は、インドの数学者マハーヴィーラが紀元850年頃に著した『数学精髄大全』の第6章、§131 1 ⁄ 2、132 1 ⁄ 2にあるとされており、指定された余りでの果物や花の連続割りを扱っている。[ 1 ]そうすると、その祖先問題は^現代に復活する1000年以上も前に存在していたことになる。中国の剰余定理を用いる割り算の問題は、紀元1世紀には中国の文献に登場している。孫子は「3、5、7で割ったときに、それぞれ余りが2、3、2となる数を見つけよ」と問いかけた。整数解を必要とする問題を紀元3世紀に初めて研究したのはアレクサンドリアのディオファントスである。このような問題の解決の基礎となる最大公約数を求めるユークリッドの互除法は、ギリシャの幾何学者ユークリッドによって発見され、紀元前 300 年に著書『原論』で発表されました。

パズルの歴史家であるデイビッド・シングマスター教授は、中世を通じて関連性の薄い一連の問題をたどっており、紀元前1700年頃のバビロニア帝国にまで遡るいくつかの言及がある。それらの問題は、山の分数または特定の数の離散物体を加算または減算し、最初はいくつあった可能性があるかを問うという一般的なテーマを扱っている。同様の問題への次の言及は、ジャック・オザナムの1725年の著書「数学と物理学の再現」である。純粋数学の分野では、1770年にラグランジュが連分数の定理を解説し、それをディオファントス方程式の解に応用した。

この問題が現代の言葉に近い形で初めて記述されたのは、 1888年のルイス・キャロルの日記である。それは、テーブルの上のナッツの山を4人の兄弟が順番に割り、そのたびに1つ余ったものを猿に与え、最後の割り算で残りがゼロになるというものである。この問題はキャロルの出版された著作には一度も登場していないが、他の参考文献^{[どれ? ]}から、この問題は1888年には流通していたようだ。ほぼ同一の問題がWWラウス・ボールの『初等代数』（1890年）に登場している。^[要出典]この問題は当時の数学者の著作で言及されており、その解答はほとんどが間違っていたことから、この問題が当時は新しく、馴染みのなかった問題であったことがわかる。^[要出典]

この問題は、アメリカの小説家であり短編小説家でもあるベン・エイムズ・ウィリアムズが古い問題を改変し、1926年10月9日発行のサタデー・イブニング・ポスト紙に掲載された「ココナッツ」という作品に取り上げたことで有名になった。^{[2]ウィリアムズ[3]}は、この問題を次のように述べた（要約および言い換え）。

5 人の男と 1 匹の猿が難破して島に漂着しました。彼らは最初の 1 日を食料としてココナッツを集めることに費やしました。

夜中に、一人の男が目を覚まし、自分の分を早く取ろうと決めました。そこで、彼はココナッツを5つの山に分けました。残ったココナッツを1つ、サルにあげました。そして、自分の山を隠し、残りを元通りにしました。

やがて、5人の男たちはそれぞれ目を覚まし、順番に同じことをしました。それぞれが、目覚めたときに山になっていたココナッツの5分の1を取って、残り1つを猿に渡しました。朝になって、残ったココナッツを分けると、5等分になりました。もちろん、全員がココナッツがなくなったことを知っていたに違いありません。しかし、全員が他の人と同じように罪を犯していたので、何も言いませんでした。

元々の山にはココナッツがいくつありましたか?

ウィリアムズは記事に答えを書いていなかった。雑誌には、問題の答えを求める2,000通以上の手紙が殺到した。ワシントン・ポスト紙の編集者ホレス・ロリマーは、ウィリアムズに「マイクにお願い、ココナッツは何個ある？ 地獄がここに現れている」という電報を送った。ウィリアムズはその後20年間、解決策を求める手紙や新しい解決策を提案する手紙を受け取り続けた。^[3]

マーティン・ガードナーは、1958年4月のサイエンティフィック・アメリカン誌の「数学ゲーム」コラムでこの問題を取り上げました。ガードナーによると、ウィリアムズは古い問題に手を加えて、より混乱を招きやすくしたそうです。古いバージョンでは、最後の割り算で猿の代わりにココナッツが使われていましたが、ウィリアムズのバージョンでは、朝の最後の割り算が偶数になります。しかし、入手可能な歴史的証拠からは、ウィリアムズがどのバージョンを入手できたかはわかりません。^[4]ガードナーはかつて、息子のジムに、これは自分のお気に入りの問題だと言いました。^[5]彼によると、「猿とココナッツ」は「おそらく最も取り組まれ、最も解かれていない」ディオファントスパズルです。^[2]それ以来、ウィリアムズ版の問題はレクリエーション数学の定番となっています。^{[6]この問題を含む元のストーリーは、}クリフトン・ファディマンの1962年のアンソロジー「数学マグパイ」 [ ^7] に完全に再録されました。この本は、アメリカ数学協会が学部生の数学図書館に購入を推奨しています。^[8]

文献には船員、猿、ココナッツの数を変えた数多くの変種が登場している。^[9]

1928年以降、元の問題とウィリアムズ修正の両方に対して数多くの解答が発表されている。^{[11] [12] [13] [14]}

問題の解決に入る前に、2、3 点注意する必要があります。5 を 6 回に分けて割り算すると、剰余がない場合は、5 ⁶ =15,625 個のココナッツが山になければなりません。6 回目で最後の割り算では、各船員は 1024 個のココナッツを受け取ります。6 回のすべての割り算が偶数になるような正の数はこれより小さくなりません。つまり、問題では、15,625 の倍数を山に追加しても、問題の条件を満たすことになります。また、元の山のココナッツの数は 15,625 より小さいことも意味します。そうでない場合は、15,625 を引くと、より小さい解が得られます。ただし、元の山の数は 5 や 10 のようにごく小さいわけではなく (これが難しい問題である理由です)、数百または数千の可能性があります。多項式根を推測する場合の試行錯誤とは異なり、ディオファントス根の試行錯誤では明らかな収束は得られません。解決策が何であるかを予測する簡単な方法はありません。

マーティン・ガードナーの1958年の数学ゲームコラムでは、ウィリアムズのバージョンよりも簡単な元の問題（朝にもココナッツが1個残っている）を解くことから分析を始めています。朝に5等分した後に各船員が受け取ったココナッツの数をFとします。すると、朝の分割前に残っているココナッツの数は、5人目の船員が目覚めたときに残っていた数は、4人目の船員が目覚めたときに残っていた数は、というように続きます。元の山のサイズNは、ディオファントス方程式^{[3]を満たしていることがわかります。}${\displaystyle 5F+1}$${\displaystyle {\tfrac {5}{4}}(5F+1)+1={\tfrac {25}{4}}F+{\tfrac {9}{4}}}$${\displaystyle {\tfrac {5}{4}}({\tfrac {25}{4}}F+{\tfrac {9}{4}})+1={\tfrac {125}{16}}F+{\tfrac {241}{16}}}$

${\displaystyle 1024N=15625F+11529}$

ガードナーは、この方程式は「試行錯誤で解くには難しすぎる」と指摘しているが^{[3] 、}ポール・ディラック経由のJHCホワイトヘッドの功績である解法を提示している。^[3]この方程式には負の整数に対する解もある。いくつかの小さな負の数を試してみると、解が得られる。^[15]最小の正の解を得るには、Nに15625、 Fに1024を加える。 ${\displaystyle N=-4,F=-1}$${\displaystyle N=15621,F=1023}$

試行錯誤ではウィリアムズのバージョンを解決できないため、より体系的なアプローチが必要です。

問題の構造を観察することで、探索空間を徐々に大きな係数で縮小し、少しの試行錯誤で解決法を見つけることができます。朝の部で各人が受け取ったココナッツの数から始めると、探索空間ははるかに小さくなります。なぜなら、その数は元の山の数よりもはるかに少ないからです。

朝の最後の割り算で各船員が受け取るココナッツの数をFとすると、朝の山は 5 Fになりますが、これは 4 で割り切れるはずです。なぜなら、夜に最後の船員が朝の割り算のために 4 つの山を結合したからです。したがって、朝の山 (数nと呼びます) は 20 の倍数です。最後の船員が起きる前の山は、5/4( n )+1 だったに違いありません。夜に起きた船員が 1 人だけであれば、元の山のココナッツの最小数は 5/4(20)+1 = 26 です。しかし、2 人の船員が起きた場合、26 は 4 で割り切れないので、朝の山は、最後の船員が起きる前の山が 4 で割り切れる 20 の倍数でなければなりません。たまたま、船員が 2 人の場合は 3*20=60 になります。つまり、nの再帰式を2 回適用すると、元の山のココナッツの最小数は 96 になります。 96 はまた 4 で割り切れるので、3 人の船員が目覚めた場合、山は 121 個のココナッツになります。しかし、121 は 4 で割り切れないので、4 人の船員が目覚めた場合、別の飛躍が必要です。この時点で、類推はわかりにくくなります。4 人の船員が目覚めるようにするには、朝の山は 60 の倍数でなければならないからです。粘り強く考えれば、17*60=1020 でうまくいき、元の山の最小の数は 2496 であることが分かるかもしれません。2496 を 5 人の船員が目覚めた場合の最後の反復、つまり 5/4(2496)+1 により、元の山は 3121 個のココナッツになります。

もう 1 つの方法は、分割プロセスを明確にするために追加のオブジェクトを使用することです。夕方に、青いココナッツを 4 個山に加えたとします。すると、最初に目覚めた船員は、ココナッツが 1 個余るのではなく、山が 5 で均等に割り切れることに気付くでしょう。船員は、青いココナッツがそれぞれ異なる 5 分の 1 になるように山を 5 等分します。次に、青いココナッツのない 5 分の 1 を取り、ココナッツの 1 個を猿に渡し、残りの 4 つの 5 分の 1 (青いココナッツ 4 個すべてを含む) を元に戻します。各船員も同じことを行います。朝の最後の分割では、青いココナッツは横に残され、誰のものでもなくなります。山全体が夜間に 5 回均等に分割されたので、山には 5 個の^{ココナッツ}、つまり青いココナッツ 4 個と普通のココナッツ 3121 個が含まれていたことになります。

分割の概念化を助けるために追加のオブジェクトを使用するという手法は、1912年にノーマン・H・アニングによる解決策としてすでに登場していた。^{[3] [16]}

17 頭の相続パズルにも、これに関連した仕掛けが登場します。ある男が 3 人の息子に 17 頭の馬を遺贈し、長男が半分、次男が 3 分の 1、末っ子が 9 分の 1 ずつ受け取るように指定します。息子たちは困惑し、賢い馬商人に相談します。商人は「さあ、私の馬を借りて」と言います。息子たちは馬を適切に分配し、すべての分配が均等になり、1 頭の馬が余ったことを発見し、商人に返します。

割り算と引き算を 5 進法で実行すると、簡単な解法が浮かび上がります。最初の船員が自分の取り分 (と猿の取り分) を取るときの引き算を考えてみましょう。n ₀、n ₁、... を元の山のココナッツの数 N の桁、s ₀、s ₁、... を船員の取り分 S の桁 (どちらも 5 進法) とします。猿の取り分を取った後、N の最下位桁は 0 になります。引き算の後、最初の船員が残した N' の最下位桁は 1 になるはずです。したがって、次のようになります (N と S の実際の桁数は不明ですが、現時点では無関係です)。

5 4 3 2 1 0（5）​​​​
  s 4 s 3 s 2 s 1 s 0    (S 5 )
          1 (N' 5 )

0 から 5 を引いて 1 になる数字は 4 なので、s ₀ =4 です。しかし、S は (N-1)/5 なので、5 ₅で割ると数字が 1 つ右にシフトするだけなので、n ₁ =s ₀ =4 です。したがって、減算は次のようになります。

5 4 3 2 4 0​​​
  s 4 s 3 s 2 s 1 4
          1

次の船員が N' に対して同じことを行うので、N' の最下位桁はサルに 1 を投げた後 0 になり、同じ理由で S' の LSD は 4 でなければなりません。つまり、N' の次の桁も 4 でなければなりません。つまり、次のようになります。

5 4 3 2 4 0​​​
  s 4 s 3 s 2 s 1 4
        4 1

n ₁ (現在は 4) から 1 を借りると 3 になるので、s _{1 は}4 でなければならず、したがって n ₂も 4 になります。つまり、次のようになります。

5 4 3 4 4 0​
  s 4 s 3 s 2 4 4
        4 1

しかし、N に適用されたのと同じ推論が N' にも適用されるため、N' の次の桁は 4 なので、s ₂と n ₃も 4 になります。5 つの除算があります。最初の 4 つは、次の除算のために 5 を底とする奇数を山に残す必要がありますが、最後の除算は 5 を底とする偶数を山に残す必要があります。そのため、朝の除算は偶数 (5 の倍数) になります。したがって、LSD が 1 の後に N には 4 つの 4 があります。N=44441 ₅ =3121 ₁₀

単純な数値分析は次のようになります。N が初期数である場合、5 人の船員のそれぞれが元の山を次のように移行します。

N => 4(N–1)/5 または同等、N => 4(N+4)/5 – 4。

この遷移を 5 回繰り返すと、朝に残っている数が得られます。

N => 4(N+4)/5 – 4

   => 16(N+4)/25 – 4

   => 64(N+4)/125 – 4

   => 256(N+4)/625 – 4

   => 1024(N+4)/3125 – 4

その数は整数でなければならず、1024 は 3125 と互いに素なので、N+4 は 3125 の倍数でなければなりません。そのような最小の倍数は 3125  · 1 なので、N = 3125 – 4 = 3121 となり、朝に残った数は 1020 となり、これは要求どおり 5 で割り切れます。

問題の再帰構造を直接利用することで、簡潔な解法が得られます。ココナッツを 5 等分し、そのたびに 1 個余りました (午前中の最後の分割は除きます)。各分割後に残った山には、必ず整数個のココナッツが含まれていなければなりません。そのような分割が 1 回だけであれば、5  · 1+1=6 が解法であることは明らかです。実際、5 の倍数プラス 1 はどれも解法であるため、考えられる一般的な式は 5  · k – 4 です。5 の倍数プラス 1 は、5 の倍数マイナス 4 でもあるためです。したがって、11、16 なども 1 回の分割に使用できます。^[17]

2 回分割する場合は、  5 ではなく5 · 5=25 の倍数を使用する必要があります。これは、25 は 5 で 2 回割り切れるためです。したがって、ココナッツの山に含まれる可能性のあるココナッツの数は、 k  · 25 – 4 です。k = 1で得られる 21 は、5 で 2 回続けて割り切れる余り 1 の最小の正の数です。5 回分割する場合は、5 ⁵ =3125 の倍数が必要であり、そのような最小の数は 3125 – 4 = 3121 です。5 回分割すると、1020 個のココナッツが残りますが、これは問題で要求されているように 5 で割り切れる数です。実際、n回分割すると、残りの山がnで割り切れることが証明されます。これは、問題の作成者が都合よく使用した特性です。

上記の議論を正式に述べると次のようになります。

元のココナッツの山は、午前中の最後の分割を除いて、合計 5 回 5 で分割され、余りは 1 になります。N は元の山のココナッツの数とします。各分割では、ナッツの数が同じ合同クラス (mod 5) に残る必要があります。したがって、

${\displaystyle N\equiv 4/5\cdot (N-1)}$(mod 5) (-1 はサルに投げられたナッツです)

${\displaystyle 5N\equiv 4N-4}$(mod 5)

${\displaystyle N\equiv -4}$(mod 5) (–4 は合同クラス)

したがって、モジュロクラス –4 のナッツで開始した場合、モジュロクラス –4 のままになります。最終的には、山を 5 回、つまり 5^5 に分割する必要があるため、元の山は 5^5 – 4 = 3121 個のココナッツでした。残りの 1020 個のココナッツは、都合よく朝の 5 で均等に分割されます。このソリューションは、本質的に、問題が (おそらく) 構築された方法を逆にします。

このバージョンに相当するディオファントス方程式は次のとおりです。

${\displaystyle 1024N=15625F+8404}$（１）

ここで、Nはココナッツの元の数、F は午前中の最後の分割で各船員が受け取った数です。これは、前の問題に対する上記の式とわずかに異なるだけで、同じ推論によって解決可能性が保証されます。

並べ替え、

${\displaystyle 1024N-15625F=8404}$（２）

このディオファントス方程式はユークリッドの互除法から直接導かれる解を持ちます。実際、この方程式は正負の周期解を無限に持ちます。(x ₀ , y ₀ )が1024x–15625y=1の解である場合、N ₀ =x ₀  · 8404、F ₀ =y ₀  · 8404は(2)の解であり、これは任意の解が次の形式を持つことを意味します。

${\displaystyle {\begin{cases}N=N_{0}+15625\cdot t\\F=F_{0}+1024\cdot t\end{cases}}}$（３）

ここで、は任意の整数値を持つことができる任意のパラメータです。 ${\displaystyle t}$

上の式(1)の両辺を1024で割ると、

${\displaystyle 1024N=15625F+8404\mod 1024}$

別の考え方としては、が整数になるためには、方程式の右辺が 1024 の整数倍でなければならないということです。この性質は、右辺から 1024 の倍数をできるだけ多く因数分解しても変わりません。両辺を 1024 の倍数で減算すると、 ${\displaystyle n}$

${\displaystyle 0=(15625F-15\cdot 1024F)+(8404-8\cdot 1024)\mod 1024}$

減算、

${\displaystyle 0=265F+212\mod 1024}$

因数分解、

${\displaystyle 0=53\cdot (5F+4)\mod 1024}$

右辺は1024の倍数でなければならない。53は1024と互いに素なので、5 F +4は1024の倍数でなければならない。そのような倍数の最小値は1 ・1024なので、5 F +4=1024、F=204となる。(1)に代入すると

${\displaystyle 1024N=15625\cdot 204+8404\Rightarrow N={\frac {3195904}{1024}}\Rightarrow N=3121}$

ユークリッドの互除法は非常に面倒ですが、積分解を必要とする有理方程式 ax+by=c を解くための一般的な方法です。上記 (2) から、1024 (2 ¹⁰ ) と 15625 (5 ⁶ ) は互いに素であり、したがってそれらの GCD は 1 であることがわかりますが、これらの 2 つの量に関して NとF を取得するには、後退代入の簡約方程式が必要です。

まず、GCD が残るまで連続した剰余を取得します。

15625 = 15·1024 + 265 (a)

1024 = 3·265 + 229 (b)

265 = 1·229 + 36 (c)

229 = 6·36 + 13 (d)

36 = 2·13 + 10 (e)

13 = 1·10 + 3 (f)

10 = 3·3 + 1 (g) (余り1は15625と1024のGCDです)

1 = 10 – 3(13–1·10) = 4·10 – 3·13 ((g)を並べ替え、(f)の3を代入して組み合わせる)

1 = 4·(36 – 2·13) – 3·13 = 4·36 – 11·13 ((e)の10を代入して組み合わせる)

1 = 4·36 – 11·(229 – 6·36) = –11·229 + 70*36 ((d)の13を代入して組み合わせる)

1 = –11·229 + 70·(265 – 1·229) = –81·229 + 70·265 ((c)の36を代入して組み合わせる)

1 = –81·(1024 – 3·265) + 70·265 = –81·1024 + 313·265 ((b)の229を代入して組み合わせる)

1 = –81·1024 + 313·(15625 – 15·1024) = 313·15625 – 4776·1024 ((a)の265を代入して組み合わせる)

したがって、ペア(N ₀ ,F ₀ ) = (-4776·8404, -313*8404)となり、NとFの両方が正になる最小値(前のサブセクションの(3)を参照)は2569なので、次のようになります。 ${\displaystyle t}$

${\displaystyle N=N_{0}+15625\cdot 2569=3121}$

${\displaystyle F=F_{0}+1024\cdot 2569=204}$

あるいは、ユークリッドの互除法に基づいて構築される連分数を使用することもできる。1024 ⁄ 15625（正確には0.065536）の連分数は[;15,3,1,6,2,1, 3 ]である。^[18]繰り返しの後に収束が止まるのは313 ⁄ 4776であり、x ₀ = –4776、y _{0 =313となる。NとFの両方が非負となる}tの最小値は2569なので、

${\displaystyle N=-4776\cdot 8404+15625\cdot 2569=3121}$。

これは問題の条件を満たす最小の正の数です。

船員の数が計算値ではなくパラメータである場合、元の山にあるココナッツの数と午前中に各船員に割り当てられた数との関係を注意深く代数的に簡約すると、係数が の式である類似のディオファントス関係が得られます。 ${\displaystyle m}$${\displaystyle m}$

最初のステップは、各船員が山を変形して残した数 に対応する再帰関係の代数展開を得ることです。${\displaystyle n_{i}}$

${\displaystyle n_{i}={\frac {m-1}{m}}(n_{i-1}-1)}$

ここで、 は元々集まった人数、 は朝に去った人数です。を回に代入して反復を展開すると、次のようになります。 ${\displaystyle n_{i\rightarrow 0}\equiv N}$${\displaystyle n_{i\rightarrow m}}$${\displaystyle n_{i}}$${\displaystyle n_{i-1}}$ ${\displaystyle m}$

${\displaystyle n_{m}=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-\left[({\frac {m-1}{m}})^{m}+...+({\frac {m-1}{m}})^{2}+{\frac {m-1}{m}}\right]}$

後者の項を因数分解すると、

${\displaystyle n_{m}=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-\left({\frac {m-1}{m}}\right)\cdot \left[({\frac {m-1}{m}})^{m-1}+...+{\frac {m-1}{m}}+1\right]}$

括弧内の形式のべき級数多項式を合計すると、 ${\displaystyle x^{m-1}+...+x+1}$${\displaystyle (1-x^{m})/(1-x)}$

${\displaystyle n_{m}=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-\left({\frac {m-1}{m}}\right)\cdot \left[\left(1-({\frac {m-1}{m}})^{m}\right){\bigg /}\left(1-({\frac {m-1}{m}})\right)\right]}$

これは次のように簡略化されます。

${\displaystyle n_{m}=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-(m-1)\cdot {\frac {m^{m}-(m-1)^{m}}{m^{m}}}}$

しかし、朝に残っている数は（つまり、朝に各船員に割り当てられた数） の倍数です。${\displaystyle n_{m}}$${\displaystyle m}$${\displaystyle F}$

${\displaystyle m\cdot F=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-(m-1)\cdot {\frac {m^{m}-(m-1)^{m}}{m^{m}}}}$

(= )を解くと、 ${\displaystyle n_{0}}$${\displaystyle N}$

${\displaystyle N=m^{m}\cdot {\frac {m-1+m\cdot F}{(m-1)^{m}}}-(m-1)}$

この方程式は 2 変数の線形ディオファントス方程式であり、 は任意の整数をとることができるパラメータです。方程式の性質とその解法は に依存しません。 ${\displaystyle N}$${\displaystyle F}$${\displaystyle m}$${\displaystyle m}$

ここで数論的考察が適用されます。 が整数であるためには、 が整数であれば十分です。したがって、 とします。 ${\displaystyle N}$${\displaystyle {\frac {m-1+m\cdot F}{(m-1)^{m}}}}$${\displaystyle r}$

${\displaystyle r={\frac {m-1+m\cdot F}{(m-1)^{m}}}}$

方程式は、解が定式化される 形式に変換する必要があります。したがって、次のようになります。${\displaystyle ax+by=\pm 1}$

${\displaystyle (m-1)^{m}\cdot r-m\cdot s=-1}$、 どこ${\displaystyle s=1+F}$

と は互いに素なので、ベズーの恒等式により整数解が存在します。この式は次のように言い換えることができます。 ${\displaystyle m}$${\displaystyle m-1}$${\displaystyle (r,s)}$

${\displaystyle (m-1)^{m}\cdot r\equiv -1\mod m}$

しかし、( m –1) ^{m は}、 mが奇数の場合、多項式Z  · m –1 であり、 mが偶数の場合、 Z · m +1です。ここで、Zはmに単項式基底を持つ多項式です。したがって、 mが奇数の場合、 r ₀ =1が解であり、 mが偶数の場合、 r ₀ =–1が解です。  

ベズーの恒等式は周期解を与えるので、ディオファントス方程式に を代入して整理すると次のようになる。 ${\displaystyle r=r_{0}+k\cdot m}$${\displaystyle r}$

${\displaystyle N=r_{0}\cdot m^{m}-(m-1)+k\cdot m^{m+1}}$

ここで、奇数の場合は、偶数の場合は、任意の整数である。^[19]与えられた に対して、問題文の制約を満たす 最小の正の値が選択される。${\displaystyle r_{0}=1}$${\displaystyle m}$${\displaystyle r_{0}=-1}$${\displaystyle m}$${\displaystyle k}$${\displaystyle m}$${\displaystyle k}$${\displaystyle N}$

ウィリアムズ版の問題では、は船員 5 人なので は1 であり、最小の正の答えを得るために をゼロにすることができるため、元の山にあるココナッツの数はN = 1   · 5 ^{5 – 4 = 3121 となります。(} k =–1 の場合の方程式の次の連続解は –12504 であるため、ゼロ付近での試行錯誤ではウィリアムズ版の問題は解けません。一方、元のバージョンの方程式は幸運にも小さな負の解を持っていました)。 ${\displaystyle m}$${\displaystyle r_{0}}$${\displaystyle k}$

以下は最初のいくつかの正の解の表です(は任意の非負の整数です)。 ${\displaystyle N}$${\displaystyle m}$${\displaystyle k}$

推定上の先行問題を含む他の変種には、任意の数の船員に対する関連する一般解があります。

午前の割り算でも余りが 1 になる場合、解は次のようになります。

${\displaystyle N=-(m-1)+k\cdot m^{m+1}}$

すると、ウィリアム以前の問題におけるココナッツの最小の正の数は 15,621 になります。 ${\displaystyle m=5}$${\displaystyle k=1}$

この問題の以前のいくつかの代替形式では、分割の結果が均等になり、分割後に残った山からナッツ (またはアイテム) が割り当てられました。これらの形式では、再帰関係は次のようになります。

${\displaystyle n_{i}={\frac {m-1}{m}}n_{i-1}-1}$

代替形式にも 2 つの結末があります。朝の割り算が偶数になる場合と、サルにナッツが 1 つ残る場合です。朝の割り算が偶数になる場合、一般解は同様の導出によって次のように簡略化されます。

${\displaystyle N=-m+k\cdot m^{m+1}}$

たとえば、のとき、元の山には 1020 個のココナッツがあり、夜に 4 回連続して均等に分割し、分割ごとに 1 個のココナッツをサルに割り当てると、朝には 80 個のココナッツが残り、最後の分割ではココナッツが残らない均等な結果になります。 ${\displaystyle m=4}$${\displaystyle k=1}$

朝の割り算でナッツが余ってしまった場合の一般的な解決方法は次のとおりです。

${\displaystyle N=r_{0}\cdot m^{m}-m+k\cdot m^{m+1}}$

ここで、 は奇数、は偶数です。たとえば、、のとき、元の山には 51 個のココナッツがあり、夜に 3 回連続して分割し、分割ごとに猿にココナッツ 1 個を割り当てると、朝には 13 個のココナッツが残り、最後の分割では猿にココナッツ 1 個が残ります。 ${\displaystyle r_{0}=-1}$${\displaystyle m}$${\displaystyle r_{0}=1}$${\displaystyle m}$${\displaystyle m=3}$${\displaystyle r_{0}=-1}$${\displaystyle k=1}$

正の剰余を含む異なる剰余を指定する他のポストウィリアムズ変種（つまり、サルが山にココナッツを追加する）は、文献で扱われています。解決策は次のとおりです。

${\displaystyle N=r_{0}\cdot m^{m}-c\cdot (m-1)+k\cdot m^{m+1}}$

ここで、奇数の場合は、偶数の場合は の各割り算後の余り（またはサルの数）であり、は任意の整数です（サルがココナッツを山に加える場​​合は は負になります）。 ${\displaystyle r_{0}=1}$${\displaystyle m}$${\displaystyle r_{0}=-1}$${\displaystyle m}$${\displaystyle c}$${\displaystyle k}$${\displaystyle c}$

分割ごとに人数や残りが変わるその他のバリエーションは、一般的には猿とココナッツに関連する問題の範疇外ですが、これらも同様に 2 変数の線形ディオファントス方程式に帰着します。これらの解法は同じ手法で得られ、新たな問題は生じません。

• アルキメデスの牛問題、ディオファントス問題よりかなり難しい問題
• フェルマーの最終定理は、おそらく最も有名なディオファントス方程式である。
• キャノンボール問題

• アントニック、ゲイリー(2013)。マーティン・ガードナーの『猿とココナッツ』がナンバープレイに登場。ニューヨーク・タイムズ、2013 年 10 月 7 日
• プレッチャー、デイビッド (2005)。今週の問題: 猿とココナッツ2005 年 5 月 16 日
• パパス、テオニ(1993)。『数学の喜び: あらゆる場所で数学を発見する』ワイド ワールド パブリッシング、1993 年 1 月 23 日、ISBN 0933174659 
• Wolfram Mathworld:猿とココナッツの問題
• キルヒナー、RB「一般化されたココナッツ問題」アメリカ数学月刊67、516-519、1960年。
• ファディマン、クリフトン（1962年）。『数学のカササギ』、サイモン＆シュスター
• ボゴモルニー、アレクサンダー(1996)ネガティブココナッツカットザノット

• サルとココナッツ – Numberphile ビデオ
• ココナッツ、サタデー・イブニング・ポストに掲載された記事のコピー
• 猿とココナッツ: 拡張ユークリッド互除法入門