最後に生き残るには？（円卓の騎士の問題）

質問

解き方を教えてください。円卓（丸テーブル）に騎士が座ります。何人かはわかりません。ある騎士（１番）から始めて、隣（２番）を殺し、次は（３番）飛ばして、また（４番）殺され、またひとり（５番）飛ばして、また（６番）殺され・・・最後に生き残った者がお姫さまと結ばれます。ひとりずつとばして殺されるので、テーブルを何周もするうちにだんだん騎士の数が減って行きます。
たとえば、３人のときは、２番目が殺されたあと、3番目を飛ばし、１番目が殺されるため生き残れるのは３番目に座った者です。４人のときは、１番目。５人のときは３番目、６人のときは５番目、７人だと７番、８人だと１番・・・となります。騎士の数がn人のとき、何番目に座れば生き残れるでしょうか、という問題です。どのように考え、式で表せばよいでしょうか。よろしくお願いします。

回答No.2

age_momo

一人とびで除いていくなら2進数で考えるほうが良さそうです。
例えば50人で考えて見ます。
50[d]=110010[b]
最後に残る人が
a_5*2^5+a_4*2^4+a_3*2^3+a_2*2^2+a_1*2+a_0
とします。ここでa_0～a_5は0 or 1ですね。
最初は人数に関係なく偶数つまり、a_0が0なら消えますからa_0=1は確定です。
次に消えるのは50[d]=110010[b]が偶数なら奇数、偶数なら奇数ですから
50を2進数で表した一桁目と同じである必要があります。今の場合、110010の
一桁目は0ですからa_1=0です。このように消えずに残るのは元の人数を2進数で
表した時の一つ前の桁と同じ数字になっている人となります。

a_5=1,a_4=0,a_3=0,a_2=1,a_1=0,a_0=1

つまり、二進数で100101[b]=37[d]なので37人目と分かります。
結局、nという数字を2進数で表して一桁ずらして1を加えるという
作業です。

50[d]=1『10010』[b]→『10010』0[b]→100101[b]=37[d]

6人なら
6[d]=1『10』[b]→『10』0[b]→101[b]=5[d]

これを10進数で計算するなら、n人に対して
2^(k+1) > n ≧ 2^k
となるkを用いて

(n-2^k)*2+1

と計算することになります。50なら2^6 > 50 ≧ 2^5
なので
(50-2^5)*2+1=37
です。

お礼

細かく説明いただき、ありがとうございます。もうちょっとでわかりそうな感じなんですが・・・・うーん。やっぱり私の頭では、むずかしいです。
まず、二進法をちゃんと勉強しないといけないですね。十進法で計算する式も、それであっているのはわかるのですが、なぜ、そういう式になるのかが・・・・・。うーん、むずかしいです。

回答No.1

ant-28

おそらく、ヨセフスの問題とも別名で言われています。ヨセフスの方がメジャーかもしれません。

先ほど、『ヨセフスの問題』をWikipediaで検索した結果、ありました。携帯電話からの投稿なので、URLを貼ると長くなってしまいます。
お手数ですが、papadekosさんご自身で、ページまで行っていただけると幸いです。

お礼

携帯からのご投稿、ありがとうございます！ほんとです。ありました。昔からある有名な数学パズルなんですね。ウィキペディアの記述だけ読んだだけだと私にはちょっと難しいのですが、問題の名前がわかったので、ほかのサイトも探せます。助かりました。