質問: ヨセフスの問題です。 ヨセフスの問題なのですが、調べても解き方らしいモノがなくてどう解いていいのかわからないのです。教えてください。 n人が円卓についていて、時計回りに1,2,3,...と番号付けされています。 この番号でその人を指すことにします。 ここで、1を残して2を除き、3を残して4を除き、と次々時計回りに一人おきに除いていく時、最後に残る番号j(n)はどんな関係式になるのでしょう??教えてください。
回答: まず、1からnまでの数を2進表示して縦に並べます。 そして、n=2^n+(a(n-1))2^(n-1)+....+(a1)2+(a0)、とおきます。ただし、(aj)は0か1です。 つまり、nを2進表示で1(a(n-1))...(a1)(a0) とします。 さて、数を消していきます。 まず、1からnまでの偶数が消えて行きます。それは、2進表示だと第1桁目の数が0の ものが消えて行くことになります。 そこで、もし(a0)=0なら、つぎに消えていくのは、2進表示で第2桁目が1になっている 数字になります。もし、(a0)=1なら、つぎに消えて行くのは、2進表示で第2桁目が 0になっている数字になります。 この法則は以降も成り立っているみたいです(まだ証明できていません;;)。 つまり、(aj)=0なら、第(j+1)桁目が1となっている数を消し、(aj)=1なら、第(j+1)桁目が0に なっている数を消す、という具合に。 よって、一番最後に残る数の2進表示は、第1桁目が1で、第(j+1)桁はちょうど(aj)に等しい(j=1,...,n-1)。つまり、2進表示で、 j(n)=(a(n-1))(a(n-2))...(a2)(a1) 1 となります。これは、nの2進表示を左へひとつずらして、一番大きい桁を除いて、1を足した値です。 すなわち、j(n)=2( n - 2^n ) +1 =2n - 2^(n+1) + 1。 以上のように私は答えを求めました。でもまだ途中で用いた法則が証明できていません。 この部分の証明、すぐに思い付かないので、またにします。