今回は問題は簡単だけど、奥深い問題でした。
今回のテーマは「ヨセフスの問題（ヨセフスの法）」
問題・200枚のカードを用意します。
一番上のカードは一番下に
次に一番上になったカードは破棄する。
また一番上にきたカードは一番下にして
次のカードは破棄する……
これを繰り返した時に、最後に残るカードは？
問題自体は非常にシンプル。
しかも1枚残して1枚破棄という事で、一般化もしやすいですし、
200枚なので力ずくでも何とかなってしまう。
本来は9枚下に回して10枚目を破棄など、
もっと大きな数字で使われる事が多いです。
ちなみにヨセフス自身は2つ残して1つ破棄を繰り返す
という事象を、実際に使ったという話が残っています。
解き方もある程度は推察でき、正解も導き出せました。
しかし数列を使ったアプローチをしてしまったので、
一般化が出来ませんでした。
今回の問題の場合、正解が導出出来る出来ないよりも、
一般化出来るかの方が重要度が高いです。
なぜなら一般化さえ出来れば、どんな初期条件でも
簡単に答えを導出できるようになるからです。
どんな一般化の方法が有るんだろうと思って
正解の解説を見ていたのですが……
2進数と1の補数を使ったエレガントな解法が登場。
システムについては省略しますが、法則性から導出される公式が
あまりにもかっこ良すぎて心が震えさせられました。
しかしこれに気付くのは放送時間内だけでは厳しいです。
せめて30分ぐらいは無いと厳しいですね。
一般化には2進数が使えるだなんて……
数学の奥深さをまた改めて実感できました。
PR
