外出自粛中でも楽しく過ごす!QAまとめ>>

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

n人が円卓についていて、時計回りに1,2,3,…と番号付けされています。
この番号でその人を指すことにします。
ここで、1を残して2を除き、3を残して4を除き、と次々時計回りに一人おきに除いていく時、最後に残る番号J(n)はどんな関係式になるのでしょう??教えてください。

A 回答 (5件)

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


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

やっぱり、そういう混乱を招いてしまったか^^;。
No.2で述べたJ(n)の式のNと、答えの出し方で出てきたNは一つずれてます。答えの出し方で用いた方が一つ大きいのです。よく読んでもらえれば、わかると思うんですが、No.4で、
「…n=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.4のように
2^(N-1)<n<2^N をみたすNを使わなかったかというと、それを使ってしまうと、先の文章のnの2進展開式が、
n=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」
が結論です。
    • good
    • 0

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

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

--------------------------

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

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

まず、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。

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

この回答への補足

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

補足日時:2003/05/11 11:32
    • good
    • 0
この回答へのお礼

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

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

まず、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。

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

予想 


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

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

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

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

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



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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード


人気Q&Aランキング