猿とココナッツ

「猿とココナッツ」は、ディオファントス解析学の分野における数学パズルです。砂漠の島で5人の船乗りと1匹の猿がココナッツの山を分けるという短編小説に由来しています。問題は、元の山にあるココナッツの個数を求めることです（端数のあるココナッツは不可）。この問題は、パズルを解くのに慣れていない人にとっては途方もなく難しいことで有名ですが、適切な数学的アプローチを用いれば、解は自明です。この問題は、娯楽数学の定番問題集となっています。

概要

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

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つ余りを猿に与え、最終的に1つになるというものである。この問題はキャロルの著作には一度も登場していないが、他の文献から判断すると、1888年には流通していたようだ。ほぼ同一の問題がW・W・ラウズ・ボールの『初等代数』（1890年）にも掲載されている。この問題は当時の数学者の著作にも言及されており、その多くは誤った解答が提示されていることから、当時この問題が新しく、あまり知られていなかったことがわかる。

この問題は、アメリカの小説家で短編小説家のベン・エイムズ・ウィリアムズが古い問題を改変し、1926年10月9日発行のサタデー・イブニング・ポスト誌に掲載された「ココナッツ」という作品に取り上げたことで有名になった。[ 2 ]

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

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

文献には、船員、猿、ココナッツの数を変えた数多くのバリエーションが登場している。[ 9 ]

ソリューション

ディオファントス問題

ディオファントス解析とは、整数解を必要とする有理係数方程式の研究です。ディオファントス問題では、方程式の数は未知数の数よりも少なくなります。方程式を解くために必要な「追加」情報は、解が整数であるという条件です。任意の解はすべての方程式を満たさなければなりません。ディオファントス方程式には、解が存在しないものもあれば、1つまたは有限個の解を持つもの、そして無限に多くの解を持つものもあります。

猿とココナッツは、次の形の2変数線形ディオファントス方程式に帰着する。

ax + by = c、またはより一般的には、
(a/d)x + (b/d)y = c/d

ここで、dはaとb の最大公約数である。[ 10 ]ベズーの恒等式により、この方程式が解けるのは、 dがcを割り切れる場合のみである。もしそうなら、この方程式には次の形の周期解が無限に存在する。

x = x 0 + t  · b、
y = y 0 + t  · a

ここで、( x 0 , y 0 ) は解であり、tは任意の整数をとるパラメータです。この問題は試行錯誤で解くことを意図したものではありません。この場合 、( x 0 , y 0 ) を解く決定論的な方法が存在します（本文参照）。

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

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

オリジナル版

ココナッツが1つ残ったオリジナルバージョン

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

1024北＝15625F+11529{\displaystyle 1024N=15625F+11529}

ガードナーはこの方程式は「試行錯誤で解くにはあまりにも難しすぎる」と指摘しているが[ 3 ] 、 JHCホワイトヘッド（ポール・ディラック経由）に帰属する解法を提示している。 [ 3 ]この方程式は負の整数にも解を持つ。いくつかの小さな負の数を試してみると、解が得られる。[ 15 ] Nに15625、 Fに1024を加えると、最小の正の解が得られる。 北＝−4、F＝−1{\displaystyle N=-4,F=-1}北＝15621、F＝1023{\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進数

割り算と引き算を5進法で行えば、簡単な解法が見つかる。最初の船員が自分の取り分（と猿の取り分）を取る引き算を考えてみよう。n 0 ,n 1 ,... を元の山のココナッツの数 N の桁、s 0 ,s 1 ,... を船員の取り分 S の桁（いずれも5進法）としよう。猿の取り分を取った後、N の最下位桁は0になる。引き算の後、最初の船員が残した N' の最下位桁は1になる。したがって、以下の式が成り立つ（N と S の実際の桁数は不明だが、現時点では無関係である）。 

n 5 n 4 n 3 n 2 n 1 0 (N 5 ) s 4 s 3 s 2 s 1 s 0 (S 5 ) 1 (N' 5 )

0から5を引いて1になる数字は4なので、s 0 =4です。しかし、Sは(N-1)/5なので、5で割ると数字が1つ右にずれるだけなので、n 1 =s 0 =4となります。つまり、引き算は次のようになります。 

n 5 n 4 n 3 n 2 4 0 s 4 s 3 s 2 s 1 4 1

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

n 5 n 4 n 3 n 2 4 0 s 4 s 3 s 2 s 1 4 4 1

n 1（現在は 4）から 1 を借りると3 になるので、s 1 は4 になり、したがって n 2も 4 になります。つまり、次のようになります。 

n 5 n 4 n 3 4 4 0 s 4 s 3 s 2 4 4 4 1

しかし、N'にもNと同じ論理が当てはまり、N'の次の桁は4なので、s 2とn 3も4となり、以下同様に続きます。割り算は5回あります。最初の4回は、次の割り算のために5を底とする奇数を山に残す必要がありますが、最後の割り算は5を底とする偶数を山に残す必要があります。そうすることで、朝の割り算は偶数（5の倍数）になります。つまり、LSDが1の後にNには4が4つあります。N=44441 5 =3121 10

数値的アプローチ

簡単な数値分析は次のようになります。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回に分けて5回分割し、そのたびに1個余りました（最後の分割は朝に行います）。分割後に残った山には、必ず整数個のココナッツが含まれていなければなりません。もしそのような分割が1回だけであれば、5 ・1+1=6が解であることは明らかです。実際、5の倍数に1を加えたものはどれも解となるため、一般的な公式は5 ・k -4となります。なぜなら、5の倍数に1を加えたものは、5の倍数から4を引いたものでもあるからです。したがって、11、16なども1回の分割として成り立ちます。[ 17 ]

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

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

元のココナッツの山は、午前中の最後の分割を除いて、合計5回5分割され、余りは1となります。Nは元の山のココナッツの数とします。各分割において、ココナッツの数は必ず同じ合同なクラス（mod 5）に含まれます。つまり、

北≡4/5⋅（北−1）{\displaystyle N\equiv 4/5\cdot (N-1)}（mod 5）（-1はサルに投げられたナッツです）
5北≡4北−4{\displaystyle 5N\equiv 4N-4}（mod 5）
北≡−4{\displaystyle N\equiv -4}（mod 5）（-4は合同クラス）

つまり、-4を法とするクラスで始めた場合、-4を法とするクラスのままになります。最終的にはこの山を5回、つまり5の5乗で割る必要があるため、元の山は5の5乗 - 4 = 3121個のココナッツでした。残りの1020個のココナッツは都合よく朝に5で割り切れます。この解法は、本質的に（おそらく）問題の作り方を逆転させたものです。

ディオファントス方程式と解の形

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

1024北＝15625F+8404{\displaystyle 1024N=15625F+8404}（1）

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

並べ替え、

1024北−15625F＝8404{\displaystyle 1024N-15625F=8404}（2）

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

{北＝北0+15625⋅tF＝F0+1024⋅t{\displaystyle {\begin{cases}N=N_{0}+15625\cdot t\\F=F_{0}+1024\cdot t\end{cases}}}（3）

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

還元主義的なアプローチ

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

1024北＝15625F+8404モッド1024{\displaystyle 1024N=15625F+8404\mod 1024}

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

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

減算、

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

因数分解、

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

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

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

ユークリッドの互除法

ユークリッドの互除法は非常に面倒ですが、積分解を必要とする有理方程式ax+by=cを解くための一般的な方法論です。上記(2)から、1024 (2 10 )と15625 (5 6 )は互いに素であり、したがって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 0、F 0）＝（-4776·8404、-313*8404）であり、NとFの両方が正になる最小値（前のサブセクションの（3）を参照）は2569であるため、次のようになります。 t{\displaystyle t}

N=N0+15625⋅2569=3121{\displaystyle N=N_{0}+15625\cdot 2569=3121}
F=F0+1024⋅2569=204{\displaystyle F=F_{0}+1024\cdot 2569=204}

連分数

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

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

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

一般化された解決策

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

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

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

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

nm=(m−1m)m⋅n0−[(m−1m)m+...+(m−1m)2+m−1m]{\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]}

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

nm=(m−1m)m⋅n0−(m−1m)⋅[(m−1m)m−1+...+m−1m+1]{\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]}

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

nm=(m−1m)m⋅n0−(m−1m)⋅[(1−(m−1m)m)/(1−(m−1m))]{\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]}

これを簡略化すると次のようになります。

nm=(m−1m)m⋅n0−(m−1)⋅mm−(m−1)mmm{\displaystyle n_{m}=\left({\frac {m-1}{m}}\right)^{m}\cdot n_{0}-(m-1)\cdot {\frac {m^{m}-(m-1)^{m}}{m^{m}}}}

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

m⋅F=(m−1m)m⋅n0−(m−1)⋅mm−(m−1)mmm{\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}}}}

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

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

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

ここで数論的な考察が適用される。が整数であるためには、 が整数であれば十分であるので、 とおく。 N{\displaystyle N}m−1+m⋅F(m−1)m{\displaystyle {\frac {m-1+m\cdot F}{(m-1)^{m}}}}r{\displaystyle r}

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

この方程式は、解が公式化できる形に変換されなければならない。したがって、 ax+by=±1{\displaystyle ax+by=\pm 1}

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

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

(m−1)m⋅r≡−1modm{\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 0 =1 、 mが偶数の場合にはr 0 =–1が解となります。  

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

N=r0⋅mm−(m−1)+k⋅mm+1{\displaystyle N=r_{0}\cdot m^{m}-(m-1)+k\cdot m^{m+1}}

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

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

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

m{\displaystyle m}N{\displaystyle N}
2 11+k⋅8{\displaystyle 11+k\cdot 8}[ 20 ]
3 25+k⋅81{\displaystyle 25+k\cdot 81}
4 765+k⋅1024{\displaystyle 765+k\cdot 1024}
5 3121+k⋅15,625{\displaystyle 3121+k\cdot 15,625}
6 233,275+k⋅279,936{\displaystyle 233,275+k\cdot 279,936}
7 823,537+k⋅5,764,801{\displaystyle 823,537+k\cdot 5,764,801}
8 117,440,505+k⋅134,217,728{\displaystyle 117,440,505+k\cdot 134,217,728}

その他のバリエーションと一般的な解決策

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

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

N=−(m−1)+k⋅mm+1{\displaystyle N=-(m-1)+k\cdot m^{m+1}}

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

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

ni=m−1mni−1−1{\displaystyle n_{i}={\frac {m-1}{m}}n_{i-1}-1}

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

N=−m+k⋅mm+1{\displaystyle N=-m+k\cdot m^{m+1}}

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

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

N=r0⋅mm−m+k⋅mm+1{\displaystyle N=r_{0}\cdot m^{m}-m+k\cdot m^{m+1}}

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

ウィリアムズ以降の変種では、正の剰余（例えば、サルがココナッツを山に加える）を含む様々な剰余を指定するものが文献で取り上げられています。解法は以下のとおりです。

N=r0⋅mm−c⋅(m−1)+k⋅mm+1{\displaystyle N=r_{0}\cdot m^{m}-c\cdot (m-1)+k\cdot m^{m+1}}

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

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

参照

参考文献

  1. ^デイヴィッド・シンマスター著『レクリエーション数学年表』
  2. ^ a bプリーチャー（2005）
  3. ^ a b c d eマーティン・ガードナー(2001). 『The Colossal Book of Mathematics』 WW Norton & Company. pp.  3– 9. ISBN 0-393-02023-1。
  4. ^アントニック（2013）
  5. ^アントニック (2013)：「私はジムに父親の好きなパズルがあるか尋ねたところ、彼はほぼ即座にこう答えた。『サルとココナッツだよ。彼はそれがとても好きだったよ。』」
  6. ^ウルフラム マスワールド
  7. ^ KIRKUS REVIEW誌『The Mathematical Magpie』 1962年7月27日
  8. ^クリフトン・ファディマン著『数学のマグパイ』アメリカ数学協会、シュプリンガー、1997年
  9. ^パパス、T.「サルとココナッツ」『数学の喜び』サンカルロス、カリフォルニア州：ワイドワールド出版/テトラ、pp. 226-227 and 234、1989年。
  10. ^ dは必要であればユークリッドのアルゴリズムで求めることができる
  11. ^アンダーウッド, RS, ロバート・E・モーリッツ. 「3242」. アメリカ数学月刊誌35, no. 1 (1928): 47-48. doi:10.2307/2298601.
  12. ^キルヒナー、ロジャーB.「一般化されたココナッツ問題」アメリカ数学月刊67号6号（1960年）：516-19。doi：10.2307/2309167。
  13. ^ S. SinghとD. Bhattacharya、「ココナッツの分割について：線形ディオファントス問題」、The College Mathematics Journal、1997年5月、pp. 203-4
  14. ^ G. SalvatoreとT. Shima、「ココナッツと誠実さについて」、Crux Mathematicorum、4 (1978) 182–185
  15. ^ボゴモーリヌイ（1996）
  16. ^ノーマン・H・アニング（1912年6月）「問題部門（#288）」『スクール・サイエンス・アンド・マスマティクス』12（6）。
  17. ^特殊なケースとして、 k = 0 の場合、最初の山には -4 個のココナッツが含まれています。これは、プラスのココナッツを 1 個サルに投げた後、山には -5 個のココナッツがあるために成り立ちます。割り算をすると、残りは -4 個のココナッツになります。このような割り算を何度行っても、山の残りのココナッツの数は -4 個になります。これは「不動点」と呼ばれる数学的な例外です。このような点を持つ問題はごくわずかですが、もし存在すると、問題を解くのがはるかに容易になります。この問題のすべての解は、この不動点に 5 の倍数を足したり引いたりすることで得られます。
  18. ^方法の説明については、ここを参照してください
  19. ^ガードナーは、 が偶数の場合に非標準的な を不可解に選択し、その後、周期性を不明瞭にする方法で式をリファクタリングすることで、同等だがかなり不可解な定式化を示しています。 r0=−1+1⋅m{\displaystyle r_{0}=-1+1\cdot m}m{\displaystyle m}
    奇数の場合、  m{\displaystyle m}N=(1+m⋅k)⋅mm−(m−1){\displaystyle N=(1+m\cdot k)\cdot m^{m}-(m-1)}
    たとえ、m{\displaystyle m}N=(m−1+m⋅k)⋅mm−(m−1){\displaystyle N=(m-1+m\cdot k)\cdot m^{m}-(m-1)}
    ここで、 は任意の整数を取ることができるパラメータです。k{\displaystyle k}
  20. ^ N =3 は方程式を満たしますが

出典

「 https://en.wikipedia.org/w/index.php?title=The_monkey_and_the_coconuts&oldid=1314391183」より取得