ヨセフスの問題（ヨセフスのもんだい、）は、計算機科学および数学の理論的問題のひとつ。ジョセファスの問題とも。formula_1 人の人間が円を描くように並び、処刑されるのを待っている。最初の人をスキップし、さらに formula_2 人をスキップし（つまり、formula_3 人をスキップして "k"番目の人に到達する）、"k"番目の人を処刑する。そしてそこから、再度 formula_3 人をスキップして "k"番目の人を処刑する。これを延々と続け（円は徐々に小さくなっていく）、最後に残った1人を釈放する。問題は、formula_1 と formula_6 が与えられたとき、起点をどこにしたら特定の人を最後まで残せるかである。ヨセフスの問題は、 が紀元370年ごろに『ユダヤ戦記』（フラウィウス・ヨセフス）をもとに書いた次のような問題が起源とされている。「ユダヤ人はローマに反抗して独立戦争を起こしたときのこと、ユダヤ側の総司令官ヨセフスは、ヨタパタの町に籠城したが、ローマ軍に包囲され46日で陥落した。同志40人と洞穴に逃れたが食料も尽きてきた。衆議は降伏を拒否し自決することで決着したが、ヨセフスと彼の友人の2人は何とか生きのびたいと思っていた。いよいよ集団自決をする段になって、ヨセフスはある方法を提案した。それは、全員を円形に並べ、3番目に位置する者が他の同志に殺してもらい、これを繰り返す。最後の一人は自殺をするというものであった。この提案にみんなが賛成したので、ヨセフスと友人は16番目と31番目に位置して助かった。」この話はヨセフスの『ユダヤ戦記』を見ると、「ヨセフスの問題」方式をとったこと以外はそのままだという。17世紀ごろの書による。これも「ヨセフスの問題」とよばれることが多い。「あるとき、キリスト教徒15人と異教徒であるトルコ人15人の乗る船が難破した。積荷を捨てて船を軽くしたが、まだ危険であった。ここで、船長は、15人は犠牲となって海に飛び込んでほしいといい、乗客を次のように輪に並べた。まず、キリスト教徒13人、トルコ人15人を環状に並べ、船長が数えて9人目ごとに海へ身を投じることとした。そして、うまく並べキリスト教徒全員を助けた。」日本では、同様な話を、「継子算法」とか「ままこ立て」と呼んでいる。室町時代の本の中に、鎌倉末期に編纂したものと考えられている『吾妻鏡』をもとに、「西行法師が、源頼朝からもらった銀の眠り猫を、頼朝邸の門前で遊んでいた子に『継子算法』の要領であげてしまったと載っている。『徒然草』（吉田兼好）や、『塵劫記』（吉田光由）にあるほか、関孝和も研究したことが伝わっている。考案者は不明。まず、formula_7 の場合の解法を示す（formula_8 の場合については、概要を後述）。ここでは再帰的な解法を示す。formula_1 人で始める場合の生き残り（の番号）を返す関数を formula_10 とする（formula_7）。最初の1周で、全ての偶数番号の人が処刑される。2周目で、新たな2番目の人が処刑され、さらに新たな4番目の人が処刑され、と続く。最初の人数が偶数の場合、2周目で formula_12 番目の人は1周目では formula_13 番目に位置している（formula_12 は任意）。したがって、formula_10 番目の人は最初は formula_16 番目に位置している。このことから、次の漸化式が得られる。最初の人数が奇数の場合、1周目の最後に1番の人が処刑される。その後、2周目では新たな2番目の人が処刑され、新たな4番目の人が処刑され…と続く。この場合、formula_12 番目の人は最初は formula_19 番目に位置していたことになる。以上から次の漸化式が得られる。formula_1 とそれに対応する formula_10 の値を表にしてみると、次のようなパターンが出現する。これを見ると、formula_10 は奇数の増加する数列であり、インデックス "n" が 2 のべき乗のときに formula_24 にリセットされると思われる。したがって、formula_25 かつ formula_26 となるような "m" と "l" を選択したとき、formula_27 となる。上の表にある値は、この式に当てはまる。しかし、数学では厳密な証明が求められる。以下に帰納法による証明を示す。定理: formula_25 かつ formula_26 なら、formula_30 である。証明: formula_1 についての数学的帰納法を用いる。まず、formula_32 では真である。formula_1 が偶数の場合と奇数の場合に分けて考える。formula_1 が偶数の場合、formula_35 かつ formula_36 となるよう formula_37 と formula_38 を選択する。ここで、formula_39 である。したがって、上述の漸化式から formula_40 となり、この2番目の等号は帰納仮説によるものである。formula_1 が奇数の場合、formula_42 かつ formula_36 となるよう formula_37 と formula_38 を選択する。ここで、formula_46 である。したがって、formula_47 となり、この2番目の等号は帰納仮説によるものである。（証明終）最も簡潔な解法は二進法で formula_1 を表す方法である。formula_10 は formula_1 を1ビット左に循環シフトさせることで得られる。formula_1 を二進法で表したものを formula_52 としたとき、解は formula_53 となる。これの証明は formula_1 を formula_55 と表現する方法を使って得られる。"k" を限定しない問題の最も簡単な解法は、動的計画法を使ったものである。次のような漸化式を用いる。formula_56、 ただし formula_57これは、formula_58 から formula_1 に増やしたときに生存者の番号がどう変化するかを考えれば明らかである。この手法の計算量は formula_60 だが、formula_6 が小さく formula_1 が大きい場合にはもっと効率的な手法がある。それは、最初のステップで "k"番目、2"k"番目、…、formula_63 番目の人を処刑し、番号付けを変更するというもので、formula_64 になる。

出典:wikipedia