今日もコマネチ大学。

今日もまたやってきましたコマネチ大学数学科。

今日の問題は、初めから言っておきますが結局できませんでした。
力ずくでは出たのですが・・・。

今日のテーマは、”ヨセフスの問題”というもの。

ユダヤ人はローマに反抗して独立戦争を起こしました。
ユダヤの総司令官ヨセフスは、ヨタパタの町に籠城したが、ローマ軍に包囲され４６日で陥落、
仲間４０人と洞穴に隠れた。ヨセフスと彼の友人は何とか生き延びたいと思っていたが、
他のものは自決を望んだ。いよいよ集団自決をする段になって、ヨセフスは全員を円形に並べ、
３番目ごとに他の同士に殺してもらい、最後の一人は自殺をするという方法を提案した。
これが認められたのでヨセフスと友人は１６番目と３１番目に位置し助かったという。

－高木茂男著”パズル遊びへの招待”－

という事を踏まえた今回の問題。

Ｑ：200枚のカードが1から順に並んでいます。
　　1番上のカードを1番下に回し、次のカードを捨てる作業を繰り返すとき
　　最後に残るカードは？

これが結構難問。
自力で1から順番に数えて考えれば出るのですが、
それを数学を使ってとこうとするとちょっと厄介です。
私もまんまと度つぼにはまってしまいました。
初め等差数列を元に考えていこうと思ったのですが、どうも上手くいかない。

答えを聞けばまあ納得なんですが・・・。
ちなみに答えは「１４５」

今回の問いについては、カードの枚数が偶数になったときと奇数になったときの
場合分けをしなくてはならないのところがミソだったんですね。私もここでやられました。(笑)

細かいところは割愛しますが、考え方はこんな感じ。
今、p枚あるカードの中から最後に残るカードをf(p)とあらわすとき

偶数の場合には、　f(p)= 2f(p/2) -1
奇数の場合には、　f(p)= 2f(p/2) +1

という関係が成り立っています。
今の場合だとf(200)なので、まずf(100)が分からなくてはならないことになります。
順番に考えると、f(50)はf(25)を分からないといけない。ここで、次は2で割れないから
順番に後ろへ回していたカードをずらしていかなくてはならないことになります。
それで次に考えるのがf(25)のときf(12)…　で結局はf(3)を分かればOK。

これはすぐに出せるのでまた順番に考えると、答えに行き着くということです。
パッとやってできる問題ではちょっとないですね。(笑)

他にも2進法を使うとき方についてやっていましたが、もう疲れちゃって。

問題の言っている内容というのは到って単純なんですけどねえ。
200だからまだ自力でやれそうですが、これが多くなってくるとやっぱり
計算式知っていないとちょっと苦しいかな。

頭の体操には中々だと思います。
今週もまた脳みそフル回転でございました。

ライフスタイルが変わる！ ⇒ http://www.thebluesky.jp/l-style/