解き方を教えてください。円卓(丸テーブル)に騎士が座ります。何人かはわかりません。ある騎士(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で質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・14歳の自分に衝撃の事実を告げてください
- ・架空の映画のネタバレレビュー
- ・「お昼の放送」の思い出
- ・昨日見た夢を教えて下さい
- ・【お題】絵本のタイトル
- ・【大喜利】世界最古のコンビニについて知ってる事を教えてください【投稿~10/10(木)】
- ・メモのコツを教えてください!
- ・CDの保有枚数を教えてください
- ・ホテルを選ぶとき、これだけは譲れない条件TOP3は?
- ・家・車以外で、人生で一番奮発した買い物
- ・人生最悪の忘れ物
- ・【コナン30周年】嘘でしょ!?と思った○○周年を教えて【ハルヒ20周年】
- ・ハマっている「お菓子」を教えて!
- ・最近、いつ泣きましたか?
- ・夏が終わったと感じる瞬間って、どんな時?
- ・10秒目をつむったら…
- ・人生のプチ美学を教えてください!!
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・都道府県穴埋めゲーム
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
ミリグラム(mg)からグラム(g...
-
5トンの水は、何㎥になるのでし...
-
この問題なぜ答えが有効数字2桁...
-
化学
-
消毒薬の計算方法 を教えてく...
-
数学の問題について質問です。...
-
0.999…(無限)と端数処理
-
50%+50%=○○
-
【至急】今日情処のテストがあ...
-
数学 総コレステロール 計算
-
ファクターの求め方
-
ジアンミン銀(I)イオンの反応
-
中和滴定によるファクターの計...
-
シュウ酸のモル濃度の求め方
-
硫酸の安全な中和方法は?
-
ヨウ化カリウム水溶液に塩素を...
-
なぜ、アンモニアと塩酸の中和...
-
水酸化ナトリウム水溶液の安全...
-
質量パーセントと重量パーセント
-
0.1M 塩酸水溶液の作り方なんで...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
おすすめ情報