ヨセフスの問題 浜学園 公開 算数 最後の大問（表現を変更）

ヨセフスの問題とか継子立ての問題といわれている古典問題

大きな円周上に、156本の木が1番から156番まで番号が書かれて等間隔で植えられている。今から、１本飛びに、木を切り倒していく。最初に2番の木を切り倒して、次に4番の木を切り倒して、78番目に156番の木を切り倒す。最後の木を切ったあとも、1本飛ばしで、順々に木を切り倒していく。切り倒し方の順番を今一度別の言葉で説明すれば、2番目の木を最初に切り倒し、切り倒された木から時計回りに数え始めて、また2番目の木を切り倒す。このような操作を繰り返して、最後に1本だけ残る木は何番目の木でしょうか。

一般化して考える。X本の木があるときに、最後に残る木がY番目の木だとすると、数式　F（X）＝Y　と書くこととする。

1,2,3,4,,,,2n というように、２ｎ本の木があるとする。最後に残る1本の木はF（２ｎ）と書き表せる。

さて、最初の操作で、偶数番目の木（ｎ本）が全部切り取られるので、残る木は、

1,3,5, ,,,,2n-1 の　ｎ本　が残る。

すると、気の早い話だが、今残っている奇数番号がついた木のなかのどれか1本が最後まで残ることになる（あたりまえ）。ｎ本の木で、順番に木を切り倒すと、最後に残る木が何番目かは、F（ｎ）と表されるのでしたよね。　で、次の式を理解できるかがカギですが、

F（２ｎ）＝２×F（ｎ）－１　となりますね。

たとえば　「5番」の木が最後に残ったとしたら、　一番最初の状況下では、「5番目の木が最後に残った」という表現になります。でも、一周して残っている木（残った奇数の木　ｎ本）を基準にしたら、「3番目の木が残った」とも言えるわけです。

もうひとつ大切な事。最初の木が奇数本の場合には、F(2n＋１)＝２×F（ｎ）＋１　　も成り立つのです。（説明しなくても、考えたら分かりますね。）

ここらで、試しに、20本の木が植えられていた場合を考えてみましょう。

F(２０)＝２×F（１０）－１　となる。で、F(１０)＝２×F（５）－１　ですから、　5本の木が植えられていた場合に最後に残るのが何番目か（これはきちんと書き出してみると、3番目の木が残ることになる）というと、3番目。だから、F（５）＝３、　　F（１０）＝５、　　F（２０）＝９　となりますので、9番目の木が残る、とカンタンに分かるのです。

さあ、もうこれで、仕込みは終わりました。

F（１５６）＝２×F（７８）－１               F（７８）＝２×F（３９）－１

F（３９）＝２×F（１９）＋１                  F（１９）＝２×F（９）＋１

F（９）＝２×F（４）＋１                          F（４）＝２×F（２）－１　

もうこれくらいで、大丈夫でしょう。　F（２）＝１　。（2本だけ木が植えられていて、最後に残るのは1番目の木ですね。最初に切られるのが2番目の木なのですから）。

順に入れていくと、F（４）＝１で　F（９）＝３で　F（１９）＝７で、F（３９）＝１５で、F（７８）＝２９で、F（１５６）＝５７　57番目の木が残る。