![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?5a7ff87)
解き方を教えてください。円卓(丸テーブル)に騎士が座ります。何人かはわかりません。ある騎士(1番)から始めて、隣(2番)を殺し、次は(3番)飛ばして、また(4番)殺され、またひとり(5番)飛ばして、また(6番)殺され・・・最後に生き残った者がお姫さまと結ばれます。ひとりずつとばして殺されるので、テーブルを何周もするうちにだんだん騎士の数が減って行きます。
たとえば、3人のときは、2番目が殺されたあと、3番目を飛ばし、1番目が殺されるため生き残れるのは3番目に座った者です。4人のときは、1番目。5人のときは3番目、6人のときは5番目、7人だと7番、8人だと1番・・・となります。騎士の数がn人のとき、何番目に座れば生き残れるでしょうか、という問題です。どのように考え、式で表せばよいでしょうか。よろしくお願いします。
A 回答 (2件)
- 最新から表示
- 回答順に表示
No.2
- 回答日時:
一人とびで除いていくなら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
- 回答日時:
おそらく、ヨセフスの問題とも別名で言われています。
ヨセフスの方がメジャーかもしれません。先ほど、『ヨセフスの問題』をWikipediaで検索した結果、ありました。携帯電話からの投稿なので、URLを貼ると長くなってしまいます。
お手数ですが、papadekosさんご自身で、ページまで行っていただけると幸いです。
携帯からのご投稿、ありがとうございます!ほんとです。ありました。昔からある有名な数学パズルなんですね。ウィキペディアの記述だけ読んだだけだと私にはちょっと難しいのですが、問題の名前がわかったので、ほかのサイトも探せます。助かりました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 計算機科学 2500円の人と2000円の人の集計 2 2023/08/06 07:18
- 数学 推論の回答について 初めまして。SPIの勉強をしていたところ、以下の推論問題がありました。 w,x, 5 2023/01/19 22:13
- Excel(エクセル) Excel 本人の名前だけが入った表を印刷したい。 3 2023/05/10 11:38
- 特撮 仮面ライダー龍騎好きな質問です。仮面ライダー龍騎のどこが好きですか??またなんのライダーが1番好きで 1 2023/08/27 17:27
- Java Java 配列<選挙> 4 2023/07/31 15:07
- 競馬 競馬の枠連の計算方法を教えてください。 4 2022/10/30 04:57
- Excel(エクセル) Excelの列から検索して該当する行を別シートに転記するVBA 2 2022/12/20 09:35
- いじめ・人間関係 比較 3 2022/07/26 00:22
- Java Java 南京錠 2 2023/02/04 11:46
- Excel(エクセル) 当番表の作成 2 2022/06/15 07:40
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
おすすめ情報