ヨセフスの問題
ヨセフスの問題(ヨセフスのもんだい、英: Josephus problem)は、数論的な問題であるが、ストーリー仕立であるといった点は数学パズル的でもある。ジョセファスの問題とも。アプローチにもバリエーションがある。
n {\displaystyle n} 人の人間が円を描くように並び、処刑されるのを待っている。最初の人をスキップし、さらに k − 2 {\displaystyle k-2} 人をスキップし(つまり、 k − 1 {\displaystyle k-1} 人をスキップして k番目の人に到達する)、k番目の人を処刑する。そしてそこから、再度 k − 1 {\displaystyle k-1} 人をスキップして k番目の人を処刑する。これを延々と続け(円は徐々に小さくなっていく)、最後に残った1人を釈放する。
問題は、 n {\displaystyle n} と k {\displaystyle k} が与えられたとき、起点をどこにしたら特定の人を最後まで残せるかである。
n {\displaystyle n} が奇数の場合、 ( n − 1 ) / 2 = 2 m 1 + l 1 {\displaystyle (n-1)/2=2^{m_{1}}+l_{1}} かつ 0 ≤ l 1 < 2 m 1 {\displaystyle 0\leq l_{1}<2^{m_{1}}} となるよう l 1 {\displaystyle l_{1}} と m 1 {\displaystyle m_{1}} を選択する。ここで、 l 1 = ( l − 1 ) / 2 {\displaystyle l_{1}=(l-1)/2} である。したがって、 f ( n ) = 2 f ( ( n − 1 ) / 2 ) + 1 = 2 ( ( 2 l 1 ) + 1 ) + 1 = 2 l + 1 {\displaystyle f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1} となり、この2番目の等号は帰納仮説によるものである。(証明終)
最も簡潔な解法は二進法で n {\displaystyle n} を表す方法である。 f ( n ) {\displaystyle f(n)} は n {\displaystyle n} を1ビット左に循環シフトさせることで得られる。 n {\displaystyle n} を二進法で表したものを n = b 0 b 1 b 2 b 3 ... b m {\displaystyle n=b_{0}b_{1}b_{2}b_{3}\dots b_{m}} としたとき、解は f ( n ) = b 1 b 2 b 3 ...