ヨセフス問題

コンピュータサイエンスと数学において、ヨセフス問題（またはヨセフス順列）は、特定の数え上げゲームに関連する理論的な問題です。このようなゲームは、 eeny、meeny、miny、moeといったグループから人物を選び出すために用いられます。

500人を対象としたヨセフス問題列の図。スキップ数は6。横軸は人数、縦軸（上から下）は時間（サイクル数）。生きている人は緑色で、死んでいる人は黒色で描かれている。^{[ 1 ]}

ヨセフス問題を引き起こす特定のカウントアウトゲームでは、何人かの人々が輪になって処刑を待ちます。カウントは円内の指定された地点から始まり、指定された方向に円を一周します。指定された人数が飛ばされた後、次の人が処刑されます。この手順は、残りの人々に対しても繰り返され、次の人から同じ方向に同じ人数が飛ばされ、最後の一人だけが残り、解放されます。

問題は、人数、出発点、方向、スキップする人数が与えられた場合、処刑を回避するために最初の円内の位置を選択することです。

歴史

この問題は、1世紀に生きたユダヤ人の歴史家で指導者であったフラウィウス・ヨセフスにちなんで名付けられました。ヨドファトの包囲戦に関するヨセフス自身の証言によると、彼と40人の兵士はローマ兵によって洞窟に閉じ込められました。彼らは捕らえられるよりも自殺を選び、くじ引きによる連続自殺の方法に落ち着きました。ヨセフスは、幸運かおそらくは神の手によって、彼ともう1人の男が最後まで残り、自殺するのではなくローマ人に投降したと述べています。これは、ヨセフスのユダヤ戦記（彼自身を三人称で書いている）の第3巻第8章第7部に書かれている話です。

しかし、この極度の苦難の中でも、彼はいつもの聡明さを失ってはいなかった。神の摂理に身を委ね、彼は次のように命を危険にさらした。「さあ、」と彼は言った。「あなたたちの間で死ぬことが決定されたのだから、さあ、互いの死をくじで決めよう。くじに最初に当たった者は、次に当たった者に殺される。こうして運命は我々全員に巡り来る。我々のうち誰も、自分の右の手で滅びることはない。残りの者がいなくなった後に、誰かが悔い改めて自ら命を救おうとしたら、それは不公平だからだ。」この提案は彼らに非常に正当に思われた。そして、彼らを説得してくじでこの件を決めさせると、彼は自分もくじを一つ引いた。最初に当たった者は、将軍がすぐに彼らの間で死ぬだろうと考えて、次に当たった者に自分の首をさらした。ヨセフスが共に死ねるなら、死は生よりも甘美だと彼らは考えていたのだ。しかし、彼は最後まで他の者と共に生き残った。それは偶然の産物か、それとも神の摂理によるものだったのかは定かではない。そして、彼は運命によって罪に定められることを、そしてもし最後まで生き残ったとしても、同胞の血に右手を染めることを強く望んでいなかったため、その者を説得して、自分への忠誠を誓わせ、自らも健全に生きるよう仕向けた。

— ヨセフス、『ユダヤ戦記』第3巻第8章第7節、579ページ

この偉業に用いられたメカニズムの詳細は曖昧である。ジェームズ・ダウディとマイケル・メイズによると^{[ 2 ]} 、 1612年にクロード・ガスパール・バシェ・ド・メジリアックが、男性を円陣に並べ、3ずつ数えて排除の順番を決めるという具体的なメカニズムを提案したという。^{[ 3 ]}この話は何度も繰り返されており、具体的な詳細は出典によって大きく異なる。例えば、イスラエル・ネイサン・ハーシュタインとアーヴィング・カプランスキー（1974）は、ヨセフスと39人の仲間が円陣に立ち、7人ごとに排除するという設定にしている。^{[ 4 ]}この問題の歴史は、SLザベルがフィボナッチ・クォータリー誌の編集者に宛てた手紙に記載されている。^[⁵^]

意図性について、ヨセフスは「これは神の摂理か、それとも単なる幸運か」と問いかけた。^{[ 6 ]} しかし、現存するスラヴ語写本は異なる説を述べている。ヨセフスは「巧妙に数字を数え、他の者全員を欺いた」のである。^{[ 6 ]}^{[ 7 ]} ヨセフスには共犯者がいた。問題は、生き残った最後の二人（彼らの共謀によって生存が確実となる）の順位を見つけることだった。彼は自身ともう一人の男をそれぞれ31位と16位に置いたとされている（以下 $k$ = 3）。^{[ 8 ]}

変種と一般化

中世版のヨセフス問題では、15人のトルコ人と15人のキリスト教徒が船に乗って嵐に見舞われます。船は乗客の半数を海に投げ込まなければ沈没してしまいます。30人全員が輪になり、9人ごとに1人が海に投げ込まれます。キリスト教徒は、トルコ人だけが海に投げ込まれるように、どこに立つかを決めなければなりません。^{[ 9 ]}他のバージョンでは、トルコ人とキリスト教徒の役割が入れ替わっています。

Graham、Knuth、Patashnik 1989、p. 8 は、「標準的な」変種について説明および研究しています。開始時に $n人の人がいて、2 人ごとに (以下$ $k$ = 2) 排除された場合に、最後の生存者がどこにいるかを決定します。

この問題を一般化すると以下のようになる。n人の集団からm人ごとに処刑され、p人目が生存者となるとする $。$ この $輪$ に $x$ 人が追加された場合、生存者はp + mx番目の位置（n + x以下）に位置する $。x$ が $p$ $+$ $mx$ $>$ $n$ $+$ xと $なる$ $最小$ $値$ $で$ $ある$ $場合$ $、$ $生存$ 者は $($ $p$ $+$ $mx$ $) - ($ $n$ $+$ $x$ $)$ の位置に位置する。^[¹⁰^]

解決

以下では、は最初の円内の人数を表し、は各ステップのカウントを表します。つまり、人がスキップされ、番目が実行されます。円内の人々はからまで番号が振られ、開始位置はで、カウントはを含みます。 $n$ $k$ $k-1$ $k$ $1$ $n$ $1$

k = 2

この問題は、2 人ごとに 1 人の人が殺される (すべての人が自分の左または右の人を殺す)、つまりのときに明示的に解決されます(より一般的なケースについては、以下に解決法の概要を示します)。この解決法はで再帰的に表現されます。最初に $n$ 人の人がいる場合 (および)の生存者の位置をで表します。円を 1 周目すると、偶数番号の人全員が死亡します。円を 2 周目すると、新しい 2 人目の人が死亡し、次に新しい 4 人目の人が死亡する、というように、円を 1 周目はなかったかのようになります。 $k=2$ $k\neq 2$ $f(n)$ $k=2$

当初の人数が偶数だった場合、円を2周目に $xの位置にいた人は、元々（$ $x$ のあらゆる選択において）xの位置にあったことになります。とします。今生き残ることになる人は、元々の位置にいました。このことから、次の回帰式が得られます。 $2x-1$ $n=2j$ $f(j)$ $2f(j)-1$

f(2j)=2f(j)-1\;.

初期の人数が奇数だった場合、1人目は円を一周した時点で死亡すると考えられます。2周目では、新たに2人目が死亡し、続いて4人目が死亡し、というように続きます。この場合、位置 $x$ の人物は元々位置xにいました。このことから、次の回帰式が得られます。 $2x+1$

f(2j+1)=2f(j)+1\;.

値が表にまとめられ、パターンが浮かび上がると（OEIS： A006257、上の図の一番左の青い数字の列）： $n$ $f(n)$

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$f(n)$	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1

これは、指数nが2のべき乗であるときはいつでも、がから始まる増加奇数列であることを示唆しています。したがって、mと $lを$ 、およびとなるように選択すると、となります。表の値がこの式を満たすことは明らかです。あるいは、 $l$ 人が死亡した後は人だけが残り、st人まで進むと考えることもできます。この人が生存者でなければなりません。したがって、となります。以下では、帰納法によって証明を示します。 $f(n)$ $f(n)=1$ $n=2^{m}+l$ $0\leq l<2^{m}$ $f(n)=2l+1$ $2^{m}$ $2l+1$ $f(n)=2l+1$

定理: かつならば。 $n=2^{m}+l$ $0\leq l<2^{m}$ $f(n)=2l+1$

証明: $n$ に対して強帰納法を用いる。基本ケースは真である。n $が$ 偶数の場合と奇数の $場合$ を別々に考える。 $n=1$

$n$ が偶数の場合、およびとなるおよびを選択します。となることに注意してください。 2 番目の等式は帰納法の仮定から導かれます。 $l_{1}$ $m_{1}$ $n/2=2^{m_{1}}+l_{1}$ $0\leq l_{1}$ $l_{1}=l/2$ $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$

$n$ が奇数の場合、およびとなるおよびを選びます。となる点に注意してください。この場合、2 番目の等式は帰納法の仮定から導かれます。これで証明は完了です。 $l_{1}$ $m_{1}$ $(n-1)/2=2^{m_{1}}+l_{1}$ $0\leq l_{1}$ $l_{1}=(l-1)/2$ $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$

$l$ を解くと、の明示的な式が得られます。 $f(n)$

f(n)=2(n-2^{\lfloor \log _{2}(n)\rfloor })+1

最もエレガントな形の答えは、サイズ $nの$ 2進表現です。n自身を1ビット左巡回シフトすることで得られます $。n$ $を$ 2進数でと表すと、解はとなります。この証明は、 $n$ をと表すこと、またはについて上記の式から得られます。 $f(n)$ $n=1b_{1}b_{2}b_{3}\dots b_{m}$ $f(n)=b_{1}b_{2}b_{3}\dots b_{m}1$ $2^{m}+l$ $f(n)$

実装: $n$ が人数を表す場合、安全な位置は関数（および）によって与えられます。 $f(n)=2l+1$ $n=2^{m}+l$ $0\leq l<2^{m}$

数を2進数で表すと、最初のビットは l を表し、残りのビットは $l$ を表します。例えば、⁠ ⁠の場合、その2進数表現は次のようになります。 $2^{m}$ $n=41$

n = 1 0 1 0 0 1 2 ^m = 1 0 0 0 0 0 l = 0 1 0 0 1

/** * @param n 円の中に立っている人の数* @return 処刑を生き延びる安全な位置* f(N) = 2L + 1 ただし N =2^M + L かつ 0 <= L < 2^M */ public int getSafePosition ( int n ) { // 方程式の L の値を見つけるint valueOfL = n - Integer . fastestOneBit ( n ); return 2 * valueOfL + 1 ; }

ビット単位

安全な位置を見つける最も簡単な方法は、ビット演算子を使用することです。この方法では、 $n$ の最上位ビットを最下位ビットにシフトすることで安全な位置が返されます。^{[ 11 ]}入力は正の整数でなければなりません。

n = 1 0 1 0 0 1 f(n) = 0 1 0 0 1 1

/** * @param n (41) 円の中に立っている人の数* @return 処刑を生き延びる安全な位置*/ public int getSafePosition ( int n ) { return ~ Integer .highestOneBit ( n * 2 ) & (( n << 1 ) | 1 ); // ---------------------- --- | ------------ // 最初に設定されているビットを取得します | | n を左シフトし、最後のビットを反転します// そしてその補数を取得します | | // | | // n を 2 で乗算します | // 両方のオペランドにビットをコピーする Bitwise And が存在します。}

k = 3

1997年、ローレンツ・ハルバイゼンとノルベルト・フンガービューラーは、このケースの閉じた形式を発見した。彼らは、ある定数が存在することを示した。 $k=3$

\alpha \approx 0.8111...

任意の精度で計算できる。この定数が与えられた場合、 $mを$ （またはのいずれか）を満たす最大の整数として選ぶ。すると、最終的な生存者は $\operatorname {round} (\alpha \cdot (3/2)^{m})\leq n$ $m^{\prime }=\operatorname {round} (\log _{3/2}n/\alpha )$ $m^{\prime }-1$

f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+(2

切り上げの場合、そうでない場合

1)

すべてのために。 $n\geq 5$

計算例として、ハルバイゼンとフンガービューラーは（実際にはヨセフスの問題の元々の定式化である）以下の式を計算している。 $n=41,k=3$

m^{\prime }\approx \operatorname {round} (\log _{3/2}41/0.8111)\approx \operatorname {round} (9.68)=10

\operatorname {round} (\alpha \cdot (3/2)^{m^{\prime }})\approx \operatorname {round} (0.8111\cdot (3/2)^{10})=47

そしてそれゆえ

m=9

\operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31

（切り捨てられていることに注意してください）

f(n)=3(41-31)+1=31

これは、数字の各パスを見ることで確認できます。1から41 :

1、2、4、5、7、8、10、11、13、14、16、17、19、20、22、23、25、26、28、29、31、32、34、35、37、38、40、41

2、4、7、8、11、13、16、17、20、22、25、26、29、31、34、35、38、40

2、4、8、11、16、17、22、25、29、31、35、38

2、4、11、16、22、25、31、35

2、4、16、22、31、35

4、16、31、35

16、31

31

一般的なケース

動的計画法は、一般的なケースでは、最初のステップを実行し、次に残りの問題の解を使用することで、この問題を解くために使用されます。インデックスが1から始まる場合、の人物はの位置からに移動します。ここで、 $n$ は人々の総数です。生存者の位置をとします。-人目の人が殺された後、の円が残り、次のカウントは元の問題で番号がだった人物から始まります。カウントをから開始した場合、残った円における生存者の位置はになります。開始点がであるという事実を考慮してこれをシフトすると、再発式が得られます^[¹²^] $s$ $((s-1){\bmod {n}})+1$ $f(n,k)$ $k$ $n-1$ $(k{\bmod {n}})+1$ $f(n-1,k)$ $1$ $(k{\bmod {n}})+1$

f(n,k)=((f(n-1,k)+k-1){\bmod {n}})+1,{\text{ with }}f(1,k)=1\,,

よりシンプルな形をとる

g(n,k)=(g(n-1,k)+k){\bmod {n}},{\text{ with }}g(1,k)=0

代わりに、位置がからまで番号付けされている場合。 $0$ $n-1$

このアプローチは実行時間ですが、小規模および大規模の場合は別のアプローチがあります。2つ目のアプローチも動的計画法を用いますが、実行時間です。これは、k人目、2 k人目、…人目の殺害を 1 ステップとみなし、その後番号を変更するというものです。 $O(n)$ $k$ $n$ $O(k\log n)$ $(\lfloor n/k\rfloor k)$

この改善されたアプローチは、

g(n,k)={\begin{cases}0&{\text{if }}n=1\\(g(n-1,k)+k){\bmod {n}}&{\text{if }}1<n<k\\{\begin{Bmatrix}g(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k)-n{\bmod {k}}+n&{\text{if }}g(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k)<n{\bmod {k}}\\\lfloor {\frac {k(g(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k)-n{\bmod {k}})}{k-1}}\rfloor &{\text{if }}g(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k)\geq n{\bmod {k}}\end{Bmatrix}}&{\text{if }}k\leq n\\\end{cases}}

参照

FLAMES（ゲーム）

参考文献

引用

^ R.Ugalde, Laurence. 「Fōrmulæプログラミング言語におけるJosephus問題」 . Fōrmulæ . 2021年7月26日閲覧。
^ダウディ＆メイズ 1989、125ページ。
^バシェ1612、174ページ。
^ハーシュタイン＆カプランスキー 1974年、121～126頁。
^ザベル 1976、48、51ページ。
^ ^a ^bコーエン、リチャード『 歴史を創る：過去を形作ったストーリーテラー』 54ページ（サイモン＆シュスター、2022年）。
^ Hailperin, Max; Kaiser, Barbara; Knight, Karl (1999). 「3.5 応用：ヨセフス問題」(PDF) .具体的な抽象化：Schemeを用いたコンピュータサイエンス入門. Brooks/Cole Publishing Company. pp. 65– 67.
^ラウズ・ボール 1905、19ページ。
^ニューマン 1988年、2403–2405頁。
^ロビンソン 1960、47–52ページ。
^ 「ビット演算を使用したJosephus問題（Java）」 . GitHub . 2018年1月7日. 2018年1月7日閲覧。
^ Park & Teixeira 2018、1–7 ページ。

出典

バシェ、CG (1612)。問題点 Plaisants ed Delectables qui se font par les Nombres (フランス語)。
グラハム, RL;クヌース, DE ; パタシュニック, O. (1989). 『具体的な数学：コンピュータサイエンスの基礎』 . アディソン・ウェスリー. ISBN 978-0-201-14236-5。
ハースタイン, IN; カプランスキー, I. (1974). Matters Mathematical . Harper & Row. ISBN 9780060428037。
フラウィウス・ヨセフス（nd）. 『フラウィウス・ヨセフス著作集』（全3巻、挿絵入り）. ウィリアム・ウィストン訳. ロンドン: ジョージ・ラウトレッジ・アンド・サンズ.
ニューマン、JR (1988).数学の世界. 第4巻. テンプス.
Park, Jang-Woo; Teixeira, Ricardo (2018). 「連続実行ヨセフス問題」. Korean J. Math . 26 (1): 1– 7. doi : 10.11568/kjm.2018.26.1.1 .
ロビンソン, WJ (1960). 「ヨセフスの問題」. Math . Gaz . 44 (347): 47– 52. doi : 10.2307/3608532 . JSTOR 3608532. S2CID 125735054 .
ラウズ・ボール, WW (1905). 『数学的レクリエーションとエッセイ』（第2版）. ロンドン: マクミラン.
Zabell, SL (1976). 「編集者への手紙」(PDF) . Fibonacci Quarterly . 14 : 48–51 . doi : 10.1080/00150517.1976.12430596 .

さらに読む

コーメン, トーマス・H. ;レイサーソン, チャールズ・E. ;リベスト, ロナルド・L. ;スタイン, クリフォード(2001). 「第14章データ構造の拡張」.アルゴリズム入門（第2版）. MIT Press and McGraw-Hill. p. 318. ISBN 0-262-03293-7。
ダウディ、ジェームズ；メイズ、マイケル・E. (1989). 「ジョセフス順列」 .組合せ数学と組合せ計算ジャーナル. 6 : 125–130 .
ハルバイセン、L.フンガービューラー、N. (1997)。「ヨセフス問題」。J.テオール。ノンブルボルドー。9 (2): 303–318 .土井: 10.5802/jtnb.204。
Jakóbczyk, F. (1973). 「一般化されたヨセフス問題について」 . Glasow Math. J. 14 ( 2): 168– 173. doi : 10.1017/S0017089500001919 . S2CID 122980022 .
ロイド, エロール L. (1983). 「ジョセフス問題に対するO(n logm)アルゴリズム」. J. Algor . 4 (3): 262– 270. doi : 10.1016/0196-6774(83)90025-1 .
マウント、ジョン (2024年10月11日). 「デュードニーのネズミ捕りパズル」 . Win Vectorブログ. Win Vector LLC . 2024年10月12日閲覧.
Odlyzko, Andrew M.; Wilf, Herbert S. (1991). 「関数反復法とヨセフス問題」 . Glasgow Math. J. 33 ( 2): 235– 240. doi : 10.1017/S0017089500008272 . S2CID 123160551 .
Ruskey, Frank; Williams, Aaron (2010). 「ネコ科のヨセフス問題」. Lect. Not. Comp. Sci . Lecture Notes in Computer Science. Vol. 6099. pp. 343– 354. Bibcode : 2010LNCS.6099..343R . doi : 10.1007/978-3-642-13122-6_33 . ISBN 978-3-642-13121-9。ファン2010
Ruskey, Frank; Williams, Aaron (2012). 「ネコ科ヨセフス問題」. Theory Comput. Syst . 50 : 20–34 . CiteSeerX 10.1.1.157.2956 . doi : 10.1007/s00224-011-9343-6 . S2CID 2273820 .
サリバン、ショーン。エリック・インスコ (2018)。「ネコ科のヨセフス問題の変形」。arXiv : 1803.11340 [ math.CO ]。
テリオー、ニコラス (2001)。「ヨセフス問題の一般化」。ユーティリティ。数学。 (58 ) : 161–173。CiteSeerX 10.1.1.164.2015 。
ウッドハウス、デイヴィッド（1973）「拡張されたヨセフス問題」Rev. Mat. Hisp.-Amer . 33 (4): 207– 218.

外部リンク

結び目を切るジョセフスフラウィウスゲーム(Java アプレット) では、 50 個中n^番目(最大) を選択できます。
ワイスタイン、エリック・W. 「ヨセフス問題」。マスワールド。
ヨセフス問題 - Numberphile on YouTube
一般化されたヨセフス問題

[formulae.org-1] R.Ugalde, Laurence. 「Fōrmulæプログラミング言語におけるJosephus問題」 . Fōrmulæ . 2021年7月26日閲覧。

[FOOTNOTEDowdyMays1989125-2] ダウディ＆メイズ 1989、125ページ。

[FOOTNOTEBachet1612174-3] バシェ1612、174ページ。

[FOOTNOTEHersteinKaplansky1974121–126-4] ハーシュタイン＆カプランスキー 1974年、121～126頁。

[FOOTNOTEZabell197648,_51-5] ザベル 1976、48、51ページ。

[Cohen-6] コーエン、リチャード『 歴史を創る：過去を形作ったストーリーテラー』 54ページ（サイモン＆シュスター、2022年）。

[7] Hailperin, Max; Kaiser, Barbara; Knight, Karl (1999). 「3.5 応用：ヨセフス問題」(PDF) .具体的な抽象化：Schemeを用いたコンピュータサイエンス入門. Brooks/Cole Publishing Company. pp. 65– 67.

[FOOTNOTERouse_Ball190519-8] ラウズ・ボール 1905、19ページ。

[FOOTNOTENewman19882403–2405-9] ニューマン 1988年、2403–2405頁。

[FOOTNOTERobinson196047–52-10] ロビンソン 1960、47–52ページ。

[github.com-11] 「ビット演算を使用したJosephus問題（Java）」 . GitHub . 2018年1月7日. 2018年1月7日閲覧。

[FOOTNOTEParkTeixeira20181–7-12] Park & Teixeira 2018、1–7 ページ。

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[

[ 11 ]

[