ヨセフスの問題
ヨセフスの問題（ヨセフスのもんだい、英: 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] が与えられたとき、起点をどこにしたら特定の人を最後まで残せるかである。
Contents
歴史
ヨセフスの問題は、ヘゲシッポスを名乗った人物(便宜上偽ヘゲシッポスと呼ばれる)[1]が紀元370年ごろに『ユダヤ戦記』（フラウィウス・ヨセフス）をもとに書いた次のような問題が起源とされている。
「ユダヤ人はローマに反抗して独立戦争を起こしたときのこと、ユダヤ側の総司令官ヨセフスは、ヨタパタの町に籠城したが、ローマ軍に包囲され46日で陥落した。同志40人と洞穴に逃れたが食料も尽きてきた。衆議は降伏を拒否し自決することで決着したが、ヨセフスと彼の友人の2人は何とか生きのびたいと思っていた。いよいよ集団自決をする段になって、ヨセフスはある方法を提案した。それは、全員を円形に並べ、3番目に位置する者が他の同志に殺してもらい、これを繰り返す。最後の一人は自殺をするというものであった。この提案にみんなが賛成したので、ヨセフスと友人は16番目と31番目に位置して助かった。」
この話はヨセフスの『ユダヤ戦記』を見ると、「ヨセフスの問題」方式をとったこと以外はそのままだという[2]。
トルコ人とキリスト教徒の問題
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] の値を表にしてみると、次のようなパターンが出現する。
| [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\lt 2^m[/math] となるような m と l を選択したとき、[math]f(n)=2 \cdot l+1[/math] となる。上の表にある値は、この式に当てはまる。しかし、数学では厳密な証明が求められる。以下に帰納法による証明を示す。
定理: [math]n=2^m+l[/math] かつ [math]0\leq l\lt 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 \lt 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 \lt 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番目、2k番目、…、[math]\lfloor n/k \rfloor[/math] 番目の人を処刑し、番号付けを変更するというもので、[math]O(k\log n)[/math] になる。
脚注
参考文献
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 14: Augmenting Data Structures, pp.318.