走り続けるｍａｚｒａ日記

問題

２００枚のカードに、１から２００まで
番号が書いてあり、番号順に並んでいます。
（１が書いてあるカードが一番上で２００が、一番下）

１番上のカードを１番下に持っていき、
次のカードを捨てるという作業を繰り返したとき、
最後に残るカードに書いてある数字は何か答えなさい。

（解答）
まずは、地道な解法。
最初は、1,2,3,4,5,6,7,8,,,199,200と並んでいますが、

2,4,6,8,,,198,200が消えるので
残るのは、
1,3,5,7,9,11,13,15,,,197,199。

次に消えるのは
3,7,11,,,199という、４で割ると３余る数。
で、残るのは、
1,5,9,13,17,21,,,193,197。

次に消えるのは
5,13,21,,,197という、８で割ると５余る数。
で、残るのは、
1,9,17,25,33,41,,,185,193。

次に消えるのは
9,25,41,,,185という、１６で割ると９余る数。
で、残るのは、
1,17,33,49,65,,,177,193。

ですが、先ほど数列の最後の193が消えなかったことに注目すると
次に消えるのは、
1,33,65,,,193という、３２で割ると１余る数。
で、残るのは、
17,49,81,113,145,177。

で、次に49,113,177が消えて、17,81,145が残り、
次に81が消えて、17,145が残り、
最後に17が消えて、145が最後まで残るので
解答は「145」でした。

さて、もっと簡単にこれを解く方法は、
ここまでの解法で気づいたかも知れませんが
ヒントは、2,4,8,16,32で、「２進法」です。

まず、200を二進数で表すと、11001000（2）です。
ここで、11001000の0と1を逆にすると、00110111(2)
00110111(2)を十進法で表すと、
2^5+2^4+2^2+2+1＝32+16+4+2+1＝55。

これを200から引いて、200-55=145
素晴らしい！