ヨセフスの問題のソースを表示

'''ヨセフスの問題'''（ヨセフスのもんだい、{{lang-en-short|Josephus problem}}）は、[[数論]]的な問題であるが、ストーリー仕立であるといった点は[[数学パズル]]的でもある。'''ジョセファスの問題'''とも。アプローチにもバリエーションがある。

<math>n</math> 人の人間が[[円 (数学)|円]]を描くように並び、処刑されるのを待っている。最初の人をスキップし、さらに <math>k-2</math> 人をスキップし（つまり、<math>k-1</math> 人をスキップして ''k''番目の人に到達する）、''k''番目の人を処刑する。そしてそこから、再度 <math>k-1</math> 人をスキップして ''k''番目の人を処刑する。これを延々と続け（円は徐々に小さくなっていく）、最後に残った1人を釈放する。

問題は、<math>n</math> と <math>k</math> が与えられたとき、起点をどこにしたら特定の人を最後まで残せるかである。

== 歴史 ==
'''ヨセフスの問題'''は、ヘゲシッポスを名乗った人物(便宜上{{仮リンク|偽ヘゲシッポス|en|Pseudo-Hegesippus}}と呼ばれる)<ref>「本物の」教会史家{{仮リンク|聖ヘゲシッポス|en|Hegesippus_(chronicler)}}(ヘゲシップス/ヘゲシッパス)の実際の生没年はおよそ紀元110年-180年頃</ref>が紀元370年ごろに『[[ユダヤ戦記]]』（[[フラウィウス・ヨセフス]]）をもとに書いた次のような問題が起源とされている。

「[[ユダヤ戦争|ユダヤ人がローマに反抗して独立戦争を起こした]]ときのこと、ユダヤ側の総司令官ヨセフスは、ヨタパタの町に籠城したが、[[ローマ軍]]に包囲され46日で陥落した。同志40人と洞穴に逃れたが食料も尽きてきた。衆議は降伏を拒否し自決することで決着したが、ヨセフスと彼の友人の2人は何とか生きのびたいと思っていた。いよいよ集団自決をする段になって、ヨセフスはある方法を提案した。それは、全員を円形に並べ、3番目に位置する者が他の同志に殺してもらい、これを繰り返す。最後の一人は自殺をするというものであった。この提案にみんなが賛成したので、ヨセフスと友人は16番目と31番目に位置して助かった。」

この話はヨセフスの『ユダヤ戦記』を見ると、「ヨセフスの問題」方式をとったこと以外はそのままだという<ref>The War of the Jews 3.387-391　ヨセフス本人は死ぬ順番を選ぶのに「くじを引いた」としか書いておらず、どのようなルールだったかは不明。また助かったもう1人は最初から助かるつもりではなく、ヨセフスが彼を殺す番になった時に説得したという。</ref>。

=== トルコ人とキリスト教徒の問題 ===
17世紀ごろの書による。これも「ヨセフスの問題」とよばれることが多い。

「あるとき、[[キリスト教徒]]15人と異教徒である[[トルコ人]]15人の乗る船が難破した。積荷を捨てて船を軽くしたが、まだ危険であった。ここで、船長は、15人は犠牲となって海に飛び込んでほしいといい、乗客を次のように輪に並べた。まず、キリスト教徒13人、トルコ人15人を環状に並べ、船長が数えて9人目ごとに海へ身を投じることとした。そして、うまく並べキリスト教徒全員を助けた。」

=== 日本での「ままこ立て」 ===
日本では、同様な話を、「継子算法」とか「[[ままこ立て]]」と呼んでいる。[[室町時代]]の本の中に、[[鎌倉時代|鎌倉]]末期に編纂したものと考えられている『[[吾妻鏡]]』をもとに、「[[西行]]法師が、[[源頼朝]]からもらった銀の眠り猫を、頼朝邸の門前で遊んでいた子に『継子算法』の要領であげてしまった」と載っている。『[[徒然草]]』（[[卜部兼好|兼好法師]]）や、『[[塵劫記]]』（[[吉田光由]]）にあるほか、[[関孝和]]も研究したことが伝わっている。考案者は不明。

== 解法 ==
まず、<math>k=2</math> の場合の解法を示す（<math>k\neq 2</math> の場合については、概要を後述）。ここでは再帰的な解法を示す。<math>n</math> 人で始める場合の生き残り（の番号）を返す関数を <math>f(n)</math> とする（<math>k=2</math>）。最初の1周で、全ての偶数番号の人が処刑される。2周目で、新たな2番目の人が処刑され、さらに新たな4番目の人が処刑され、と続く。最初の人数が偶数の場合、2周目で <math>x</math> 番目の人は1周目では <math>2x - 1</math> 番目に位置している（<math>x</math> は任意）。したがって、<math>f(n)</math> 番目の人は最初は <math>2f(n) - 1</math> 番目に位置している。このことから、次の漸化式が得られる。

: <math>f(2n)=2f(n)-1\,</math>

最初の人数が奇数の場合、1周目の最後に1番の人が処刑される。その後、2周目では新たな2番目の人が処刑され、新たな4番目の人が処刑され…と続く。この場合、<math>x</math> 番目の人は最初は <math>2x+1</math> 番目に位置していたことになる。以上から次の漸化式が得られる。

:<math>f(2n+1)=2f(n)+1\,</math>

<math>n</math> とそれに対応する <math>f(n)</math> の値を表にしてみると、次のようなパターンが出現する。

{| class="wikitable" style="text-align: center;"
!<math>n</math>
| 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16
|-
!<math>f(n)</math>
| 1 || 1 || 3 || 1 || 3 || 5 || 7 || 1 || 3 ||  5 ||  7 ||  9 || 11 || 13 || 15 ||  1
|}

これを見ると、<math>f(n)</math> は奇数の増加する数列であり、インデックス ''n'' が 2 のべき乗のときに <math>f(n)=1</math> にリセットされると思われる。したがって、<math>n=2^m+l</math> かつ <math>0\leq l<2^m</math> となるような ''m'' と ''l'' を選択したとき、<math>f(n)=2 \cdot l+1</math> となる。上の表にある値は、この式に当てはまる。しかし、数学では厳密な証明が求められる。以下に帰納法による証明を示す。

'''定理:''' <math>n=2^m+l</math> かつ <math>0\leq l<2^m</math> なら、<math>f(n) = 2l+1</math> である。

'''証明:''' <math>n</math> についての[[数学的帰納法]]を用いる。まず、<math>n=1</math> では真である。<math>n</math> が偶数の場合と奇数の場合に分けて考える。

<math>n</math> が偶数の場合、<math>n/2 = 2^{m_1}+l_1</math> かつ <math>0\leq l_1 < 2^{m_1}</math> となるよう <math>l_1</math> と <math>m_1</math> を選択する。ここで、<math>l_1 = l/2</math> である。したがって、上述の漸化式から <math>f(n) = 2f(n/2)-1=2((2l_1)+1) - 1=2l+1</math> となり、この2番目の等号は帰納仮説によるものである。

<math>n</math> が奇数の場合、<math>(n-1)/2 = 2^{m_1}+l_1</math> かつ <math>0\leq l_1 < 2^{m_1}</math> となるよう <math>l_1</math> と <math>m_1</math> を選択する。ここで、<math>l_1 = (l-1)/2</math> である。したがって、<math>f(n) = 2f((n-1)/2)+1=2((2l_1)+1) + 1=2l+1</math> となり、この2番目の等号は帰納仮説によるものである。（証明終）

最も簡潔な解法は[[二進法]]で <math>n</math> を表す方法である。<math>f(n)</math> は <math>n</math> を1ビット左に循環シフトさせることで得られる。<math>n</math> を二進法で表したものを <math>n=b_0 b_1 b_2 b_3\dots b_m</math> としたとき、解は <math>f(n)=b_1 b_2 b_3 \dots b_m b_0</math> となる。これの証明は <math>n</math> を <math>2^m+l</math> と表現する方法を使って得られる。

''k'' を限定しない問題の最も簡単な解法は、[[動的計画法]]を使ったものである。次のような漸化式を用いる。

<math>f(n,k)=(f(n-1,k)+k) \bmod n</math>、 ただし <math>f(1,k)=0</math>

これは、<math>n-1</math> から <math>n</math> に増やしたときに生存者の番号がどう変化するかを考えれば明らかである。この手法の計算量は <math>O(n)</math> だが、<math>k</math> が小さく <math>n</math> が大きい場合にはもっと効率的な手法がある。それは、最初のステップで ''k''番目、2''k''番目、…、<math>\lfloor n/k \rfloor</math> 番目の人を処刑し、番号付けを変更するというもので、<math>O(k\log n)</math> になる。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
* {{Cite book|和書|author1=Thomas H. Cormen|author2=Charles E. Leiserson|author3=Ronald L. Rivest|author4=Clifford Stein|authorlink3=ロナルド・リベスト|title=Introduction to Algorithms|edition=Second Edition|publisher=[[マサチューセッツ工科大学出版局|MIT Press]] and [[マグロウヒル・エデュケーション|McGraw-Hill]]|year=2001|isbn=0-262-03293-7|chapter=Chapter 14: Augmenting Data Structures|pages=318}}

== 外部リンク ==
* [http://www.cut-the-knot.org/recurrence/flavius.shtml Josephus Flavius game] Javaアプレットによるゲーム
* [http://mathworld.wolfram.com/JosephusProblem.html Josephus Problem at the MathWorld encyclopedia];
* [http://mathdl.maa.org/mathDL/3/?pa=content&sa=viewDocument&nodeId=322 Josephus Problem at Shippensburg University].
{{Combin-stub}}

{{DEFAULTSORT:よせふすのもんたい}}
[[Category:組合せ論]]
[[Category:理論計算機科学]]
[[Category:数学に関する記事]]
[[Category:フラウィウス・ヨセフス]]