第六回
今回は
ヨセフス (Flavius Josephus) の問題。 これは日本では塵劫記等で 「継子立て」 として知られている。 ヨセフスの問題と呼ばれている経緯については
こことか
ここを参照のこと。
さて, 問題は次の通り
1 から 200 迄が書かれた 200 枚の cards が番号順に並んでいる。 ここで 「top の card を後ろに持って行き, その次にある card を捨てていく」 という行為を繰り返していくと, 最後に残る card には何番と書いてあるであろうか。
答だけ出すなら実験してみるのが一番である。
実際軍団は煎餅で作ってみて, 捨てる代わりに食べる, という実験を一時間二十分やった結果 145 という正解を出した。 但し, スタジオでは, どこかで手順を間違えて, 失敗していた。
東大生は数列を考えて 137 と答えた。
たけしは二進法に気付くといういい点までいったのだが, 惜しいことに, 途中で三回 (25 枚, 13 枚, 3 枚) 奇数になるという所に惑わされて正解までたどり着かなかった。 が, 二進法に気付いたというところで, 賞を貰っていた。
今, cards が p 枚ある時に, 最後の card が c(p) であるとしよう。
Case 1. 2n 枚の時
この場合は, [1, 2], [3, 4], ..., [2n - 1, 2n] と二枚ずつ組にしていくと, 各組の後ろの方だけが捨てられていき, 最後の card s は, 組の数 r によって s = 2r - 1 と表されていることが分かる。
Case 2. 2n + 1 枚の時
この場合は, 1 だけを別にして, 残りを二枚ずつ組にしていくと, 1, [2, 3], [4, 5], ..., [2n, 2n + 1] となる。 この場合は, 各組の最初の方だけが捨てられていき, 最後まで行った後, 1 が捨てられる。
従って, 最後の card s は, 組の数 r によって s = 2r + 1 と表されることになる。
以上によって c(2n) = 2c(n) - 1, c(2n + 1) = 2c(n) + 1 と表されることになる。
明らかに c(1) = 1 であるから, 再帰的に考えていって
c(200) = 2c(100) - 1, c(100) = 2c(50) - 1, c(50) = 2c(25) - 1, c(25) = 2c(12) + 1, c(12) = 2c(6) + 1, c(3) = 2c(1) + 1 = 3 から逐次代入していって, c(6) = 5, c(12) = 9, c(25) = 19, c(50) = 37, c(100) = 73, c(200) = 145 となる。
又, 数値を直接計算しないで展開すると, c(200) = 200 - ~200 (但し ~a は a の bit 反転を表す) で計算されていることが分かる。 言い換えると, 200 を二進法で表しておいて, top bit を後ろに回すのと同じである。
某所の情報に拠れば, これは中学入試で頻出だそうで, 次のように考えて答を出すのだそうだ。 200 より小さくて一番近い 2 の冪の数を探す。 この場合は 128 (= 2
7) である (先程の話で言うと, 200 の top bit の桁を見るということになる。 言い換えれば 2
[log2200]. 但し, [ ] は Gauß 記号)。 このとき 200 - 128 = 72 枚が捨てられている。 200 枚の場合捨てた 72 枚は全て偶数である。 このとき一番上にあるのは 72 番目の偶数の次の数, 即ち 72×2 + 1 = 145. これが最後まで残る数となる。

0