ヨセフスの問題です。

ヨセフスの問題なのですが、調べても解き方らしいモノがなくてどう解いていいのかわからないのです。教えてください。

ｎ人が円卓についていて、時計回りに１，２，３，…と番号付けされています。
この番号でその人を指すことにします。
ここで、１を残して２を除き、３を残して４を除き、と次々時計回りに一人おきに除いていく時、最後に残る番号Ｊ（ｎ）はどんな関係式になるのでしょう？？教えてください。

No.5 ベストアンサー 回答者： sokamone 回答日時： 2003/05/12 00:42

>2^(N-1) =< n < 2^N を満たすＮですね？

>で、J(n)=2n - 2^(N+1) + 1で実際に計算してみたんです>が、答えがマイナスになってしまうんです…。
>J(n)=2n - 2^N +1ならうまくいくんですけど。
>どういうことでしょう？？

やっぱり、そういう混乱を招いてしまったか＾＾；。
No.２で述べたJ(ｎ）の式のＮと、答えの出し方で出てきたＮは一つずれてます。答えの出し方で用いた方が一つ大きいのです。よく読んでもらえれば、わかると思うんですが、No.4で、
「…ｎ＝2^N+(a(N-1))2^(N-1)+….＋(a1)2+(a0)、とおきます。」のNは、2^N=<n<2^(N+1)を満たすNです。このときは、J(n)=2n - 2^(N+1) + 1　です。なぜ、No.４のように
2^(N-1)<n<2^N をみたすNを使わなかったかというと、それを使ってしまうと、先の文章のｎの2進展開式が、
ｎ＝2^(N-1)+(a(N-2))2^(N-2)+….＋(a1)2+(a0)、
というふうに読みにくくなるからです。しかし、2^(N-1)<n<2^N を満たすNをもちいたほうが、J(n)の式が、
J(n)=2n-2^N+1
となってすっきりするのです。お騒がせしました。

結局、
「2^(N-1)<n<2^N のとき、J(n)=2n+1-2^N」
が結論です。

No.4 回答者： sokamone 回答日時： 2003/05/10 18:05

すみません、コピーが途中からでした。

もう一度全文投稿します。

－－－－－－－－－－－－－－－－－－－－－－－－－－

siegmundさんの指示しているページでは、
No.２のguiterさんが答えを提示して、
そのあとstamachmanさんが証明をしていますね。

どうやら私の出した答えも同じなので、合っているみたいですね。
stmachmanさんの証明は（私ちょっとめんどくさがりで）読むのがしんどいので、
私がどうやって考えたのかを説明します。

まず、１からｎまでの数を２進表示して縦に並べます。
そして、ｎ＝2^N+(a(N-1))2^(N-1)+….＋(a1)2+(a0)、とおきます。ただし、(aj)は０か１です。
つまり、ｎを２進表示で1(a(N-1))…(a1)(a0) とします。

さて、数を消していきます。
まず、１からｎまでの偶数が消えて行きます。それは、２進表示だと第１桁目の数が０の
ものが消えて行くことになります。
そこで、もし(a0)=0なら、つぎに消えていくのは、２進表示で第２桁目が１になっている
数字になります。もし、（a0)=1なら、つぎに消えて行くのは、２進表示で第２桁目が
０になっている数字になります。
この法則は以降も成り立っているみたいです（まだ証明できていません；；）。
つまり、（aj)=0なら、第(j+1)桁目が１となっている数を消し、(aj)=1なら、第(j+1)桁目が０に
なっている数を消す、という具合に。
よって、一番最後に残る数の２進表示は、第１桁目が１で、第(j+1)桁はちょうど(aj)に等しい（j=1，…，N-１)。つまり、２進表示で、
J(n)=(a(N-1))(a(N-2))…(a2)(a1) 1
となります。これは、ｎの２進表示を左へひとつずらして、一番大きい桁を除いて、１を足した値です。
すなわち、J(n)=2( n - 2^N ) +1 =2n - 2^(N+1) + 1。

以上のように私は答えを求めました。でもまだ途中で用いた法則が証明できていません。
証明大変かもしれませんが、がんばって考えて下さい。

この回答への補足

あの…バカな質問でごめんなさい。
J(n)=2( n - 2^N ) +1 =2n - 2^(N+1) + 1
上の式で、ｎは円卓についた人数ですよね。
では、Ｎって何ですか？
何の数を入れればいいんでしょう？

補足日時：2003/05/11 11:32

この回答へのお礼

ああ！やっぱりわかりました。
2^(N-1) =< n < 2^N を満たすＮですね？
で、J(n)=2n - 2^(N+1) + 1で実際に計算してみたんですが、答えがマイナスになってしまうんです…。
J(n)=2n - 2^N +1ならうまくいくんですけど。
どういうことでしょう？？

お礼日時：2003/05/11 11:43

No.3 回答者： sokamone 回答日時： 2003/05/10 18:03

まず、１からｎまでの数を２進表示して縦に並べます。

そして、ｎ＝2^N+(a(N-1))2^(N-1)+….＋(a1)2+(a0)、とおきます。ただし、(aj)は０か１です。
つまり、ｎを２進表示で1(a(N-1))…(a1)(a0) とします。

さて、数を消していきます。
まず、１からｎまでの偶数が消えて行きます。それは、２進表示だと第１桁目の数が０の
ものが消えて行くことになります。
そこで、もし(a0)=0なら、つぎに消えていくのは、２進表示で第２桁目が１になっている
数字になります。もし、（a0)=1なら、つぎに消えて行くのは、２進表示で第２桁目が
０になっている数字になります。
この法則は以降も成り立っているみたいです（まだ証明できていません；；）。
つまり、（aj)=0なら、第(j+1)桁目が１となっている数を消し、(aj)=1なら、第(j+1)桁目が０に
なっている数を消す、という具合に。
よって、一番最後に残る数の２進表示は、第１桁目が１で、第(j+1)桁はちょうど(aj)に等しい（j=1，…，N-１)。つまり、２進表示で、
J(n)=(a(N-1))(a(N-2))…(a2)(a1) 1
となります。これは、ｎの２進表示を左へひとつずらして、一番大きい桁を除いて、１を足した値です。
すなわち、J(n)=2( n - 2^N ) +1 =2n - 2^(N+1) + 1。

以上のように私は答えを求めました。でもまだ途中で用いた法則が証明できていません。
この部分の証明、すぐに思い付かないので、またにします。

No.2 回答者： sokamone 回答日時： 2003/05/10 16:22

予想　

2^(N-1) =< n < 2^N を満たすＮを見付けると、
Ｊ(ｎ)=2n+1-2^N

いま証明考えてます＾＾；。
もしかしたら、まちがってるかもしれません。
難しい問題ですね。

ｎの２進表示で消えて行く数字のパターンを見つけて
Ｊ(ｎ）の２進表示の満たすべき条件を考えて、
この予想に達したんですが、途中論理ミスを発見して
いまもう一度考えているところです。
いくつかのｎで試して見たんですが、なぜか答えが
一致するので悩んでいます。

困り度３みたいなので、siegmundさんが上げているページを参考にするのが早いかもしれませんね＾＾。一応わたしも参加しようかなと…フライングぎみですが、投稿した次第です＾＾；。

No.1 回答者： siegmund 回答日時： 2003/05/10 15:07

日本では「継子立て」という名前で知られています．

http://oshiete1.goo.ne.jp/kotaeru.php3?q=49741
http://oshiete1.goo.ne.jp/kotaeru.php3?q=449260
などいかがでしょうか．