≪1000人の小人≫問題を考えてみた

宿題は 彎曲していく日常 2005/05/08 http://d.hatena.ne.jp/noharra/20050508 にあるとおり.

一般化すると N人の小人が輪になっている. 妖怪ミツハノメが(例えば右回りに)一人おきに頭を触り,頭を触られた小人は輪から消えてゆく. 最後に残るのは 誰か? id:noharra:20050508 が二進数で考えていることをヒントに -- 一周する毎に人数が半分になっていくので, 2の倍数が関係する だろう -- 考えてみる.

最初に小人の人数が (2のk乗)人の場合

【小人の人数が (2のk乗)人の輪の場合】

(1) k = 1, 2人の時

(1周目) #1, #2 → #1 が残る

(2) k = 2, 4人の時

(1周目) #1, #2, #3, #4, #1, #3

(2周目) #1, #3 → #1 が残る

(3) k = 3, 8人の時

(1周目) #1, #2, #3, #4, #5, #6, #7, #8, #1, #3, #5, #7, ……

(2周目) #1, #3, #5, #7, #1, #5

(3周目) #1, #5 → #1 が残る

(k) 以下, (2のk乗)人の時は

(1周目),(2周目), …… ,(k周目)のいずれでも #1が 残る位置を確保している → #1 が最後まで残る

と考えることができるだろう.

(2のk乗) > n > (2の(k-1)乗) の場合, どうなるかを次に考えてみた. 具体的に 10人の小人から始めてみよう.

【16>10>8 10人の時】

#1, #2, #3, #4, #5, #6, #7, #8, #9, #10と 2人が消えて 8人になったところで, (2の（k-1)乗)人の場合となる.

#5, #6, #7, #8, #9, #10, #1, #3 の8人の輪から出発して最後まで残るのは, 先頭にいる #5 となる.*1

ということで, エイヤと 1000人の場合, 誰が最後まで残るか考えてみた.

【1024>1000>512 1000人の時】

512人の輪となった時点で先頭に誰がいるかを求めればよい. 1000-512=488人が消えた時,その先頭にいるのは 488*2の次の小人 #977 である → #977 が最後まで残る*2

*1: 10人の時についての結論は, -- 求め方は異なるが -- id:noharra:20050508 と一致する.

*2: id:noharra:20050508 EXCELLさんが出した結果とは異なる, 要検討