ヨセフスの問題

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

当初の人数が偶数だった場合、円周を2周した時点で位置xにいる人は、元々は位置xにいた。${\displaystyle 2x-1}$（ xの任意の選択について）${\displaystyle n=2j}$. の人物${\displaystyle f(j)}$生き残るのは元々のポジションだった${\displaystyle 2f(j)-1}$これにより、次の式が得られます。$${\displaystyle f(2j)=2f(j)-1.}$$

初期人数が奇数だった場合、1人目は円周1周目の終わりに死亡したと考えることができます。同様に、2周目には2人目が死亡し、次に4人目が死亡する、といった具合です。この場合、位置xの人は元々位置xにいました。${\displaystyle 2x+1}$これにより、次の式が得られます。 $${\displaystyle f(2j+1)=2f(j)+1.}$$

値が表にまとめられるとき${\displaystyle n}$そして${\displaystyle f(n)}$あるパターンが浮かび上がってくる（OEIS：A006257 、また上の図の左端の青い数字の列も参照）：

これは、${\displaystyle f(n)}$は、増加する奇数列で、${\displaystyle f(n)=1}$インデックスnが2 のべき乗であるとき。したがって、mとl が次のように選ばれると、${\displaystyle n=2^{m}+l}$そして$0 ≤ l < 2 m$、 それから${\displaystyle f(n)=2l+1}$表の値がこの式を満たすことは明らかです。あるいは、l人が亡くなった後には、$2m$人々、そしてそれは${\displaystyle 2l+1}$1人目。この人が生存者でなければならない。${\displaystyle f(n)=2l+1}$以下に、帰納法による証明を示す。

定理:${\displaystyle n=2^{m}+l}$そして$0 ≤ l < 2 m$、 それから${\displaystyle f(n)=2l+1}$。

証明：nに対して強い帰納法を用いる。基本ケース${\displaystyle n=1}$これは正しい。nが偶数の場合とnが奇数の場合では、それぞれ別々に検討される。

nが偶数の場合、${\displaystyle l_{1}}$そして${\displaystyle m_{1}}$そのため${\displaystyle n/2=2^{m_{1}}+l_{1}}$そして${\displaystyle 0\leq l_{1}<2^{m_{1}}}$。 ご了承ください${\displaystyle l_{1}=l/2}$。${\displaystyle f(n)=2f(n/2)-1=2[(2l_{1})+1]-1=2l+1}$2番目の等式が帰納法の仮説から導かれる場合、この等式が成り立つ。

nが奇数の場合は、${\displaystyle l_{1}}$そして${\displaystyle m_{1}}$そのため${\displaystyle (n-1)/2=2^{m_{1}}+l_{1}}$そして${\displaystyle 0\leq l_{1}<2^{m_{1}}}$。 ご了承ください${\displaystyle l_{1}=(l-1)/2}$。${\displaystyle f(n)=2f[(n-1)/2]+1=2[(2l_{1})+1]+1=2l+1}$2番目の等式は帰納法の仮定から導かれる。これで証明は完了する。

lを解くと、明示的な式が得られます。${\displaystyle f(n)}$: $${\displaystyle f(n)=2(n-2^{\lfloor \log _{2}(n)\rfloor })+1.}$$

最も洗練された回答形式は、サイズnのバイナリ表現を用いるものです。${\displaystyle f(n)}$nを 1 ビット左巡回シフトすることで得られます。nをバイナリで表すと次のようになります。${\displaystyle n=1b_{1}b_{2}b_{3}\dots b_{m}}$すると、解は次のように与えられる。${\displaystyle f(n)=b_{1}b_{2}b_{3}\dots b_{m}1}$この証明は、 nの表現から導かれる。$2m+l$または上記の式から${\displaystyle f(n)}$。

実装: nを人数とすると、安全な位置は次の関数で与えられる。${\displaystyle f(n)=2l+1}$、 どこ ${\displaystyle n=2^{m}+l}$そして$0 ≤ l < 2 m$。

数値がバイナリ形式で表されている場合、最初のビットは$2m$残りのビットはlを表します。たとえば、 の場合${\displaystyle 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 . highestOneBit ( n ); return 2 * valueOfL + 1 ; }

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 を乗算 | // 両方のオペランドに存在するビットをコピーするためのビットごとの AND 演算}

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

${\displaystyle \alpha \approx 0.8111...}$

任意の精度で計算できる定数。この定数が与えられたとき、m を次の条件を満たす最大の整数として選択する。$\displaystyle \operatorname {round} (\alpha \cdot (3/2)^{m})\leq n}$これは${\displaystyle m^{\prime }=\operatorname {round} (\log _{3/2}n/\alpha )}$または${\displaystyle m^{\prime }-1}$そして、最後の生存者は

${\displaystyle f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+(2}$切り上げの場合、そうでなければ${\displaystyle 1)}$

すべての人々のために${\displaystyle n\geq 5}$。

計算例として、ハルベイゼンとフンガービューラーは次のように述べている。${\displaystyle n=41,k=3}$（これは実際にはヨセフスの問題の本来の定式化である）。彼らは次のように計算する。

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

$\displaystyle \operatorname {round} (\alpha \cdot (3/2)^{m^{\prime }})\approx \operatorname {round} (0.8111\cdot (3/2)^{10})=47}$そのため${\displaystyle m=9}$

$\displaystyle \operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31$（これは切り捨てられた値です）

${\displaystyle 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 から始まる場合、${\displaystyle s}$最初の人物の位置からシフトします${\displaystyle ((s-1){\bmod {n}})+1}$ここで、nは総人数である。${\displaystyle f(n,k)}$生存者の位置を示す。${\displaystyle k}$- 番目の人が殺され、${\displaystyle n-1}$残り、次のカウントは元の問題で番号が${\displaystyle (k{\bmod {n}})+1}$残りの円の中での生存者の位置は${\displaystyle f(n-1,k)}$カウントが開始される場合${\displaystyle 1}$; 開始点が${\displaystyle (k{\bmod {n}})+1}$再帰式^{[ 12 ]が得られる}$${\displaystyle f(n,k)={\big (}[f(n-1,k)+k-1]{\bmod {n}}{\big )}+1,{\text{ with }}f(1,k)=1,}$$ より単純な形をとる $${\displaystyle g(n,k)=[g(n-1,k)+k]{\bmod {n}},{\text{ with }}g(1,k)=0}$$ 位置が番号付けされている場合${\displaystyle 0}$に${\displaystyle n-1}$その代わり。

このアプローチには実行時間があります${\displaystyle O(n)}$しかし、小規模な${\displaystyle k}$そして大きい${\displaystyle n}$別の方法もあります。2番目の方法も動的計画法を使用しますが、実行時間があります。${\displaystyle O(k\log n)}$これは、 k番目、2k番目、...を殺すことを考慮に基づいている。${\displaystyle (\lfloor n/k\rfloor k)}$1 番目の人を 1 つのステップとして、次に番号を変更します。

この改良されたアプローチは、 $${\displaystyle 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\left(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k\right)-n{\bmod {k}}+n&{\text{if }}g\left(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k\right)<n{\bmod {k}}\\\left\lfloor {\dfrac {k\left(g\left(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k\right)-n{\bmod {k}}\right)}{k-1}}\right\rfloor &{\text{if }}g\left(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k\right)\geq n{\bmod {k}}\end{Bmatrix}}&{\text{if }}k\leq n.\\\end{cases}}}$$