書記が数学やるだけ#81 漸化式の応用-1（ヨセフスの問題（継子立て））

今回は中学入試でよく出る「継子立て」について，大学入試問題から見ていくことにする。これは「ヨセフスの問題」とも呼ばれるもので，漸化式を用いて解くことができる。

問題

中学入試では，いろいろな数について最後のカードが何になるかが問われ，中にはとても大きい数で問うこともあり，規則性がわかるかどうかが鍵となる。

大学入試では，それを実際に式で表す試みが問われる，これは漸化式の応用である。

解法

(1)は実際にやってみるのみ。ついでにn=9,10のときも示しておく。

とこんな感じである。

ここで，いくつかの規則性を感じると思う。中学入試では，その思う規則性に従えばいいのだが，ここでは実証してみようというのが以下の問いの意図だろう。

1周するごとに取り除かれるカードの種類について考えることで，最後に残るカードがわかる。まずは偶数枚の場合。

奇数枚の場合。

2の累乗枚の場合。

これらの規則性により，大きい数でも単純化して議論できるようになる。

以下その発祥について，Wikipediaより引用する。

継子立てについて，一般には，吉田光由『塵劫記』（1627年）に載った以下の説話によって広く知られたとされる。

ある家には、先妻の子と継母の子が、それぞれ15人ずつ、計30人いた。跡取りを決めるため、継母が一計を案じた。子供たちを交互に並べ、継母の子から右回りに数え、10番目に当たった子供を除いていくと、先妻の子ばかりが除かれていった。最後の1人になった先妻の子が「ここからは、私から左回りに数えてください」と抗議すると、今度は継母の子ばかりが除かれ、抗議したその子だけが残り、めでたく跡取りとなった。

ヨセフスの問題は，ヘゲシッポスを名乗った人物(便宜上偽ヘゲシッポスと呼ばれる)が紀元370年ごろに『ユダヤ戦記』（フラウィウス・ヨセフス）をもとに書いた次のような問題が起源とされている。

「ユダヤ人はローマに反抗して独立戦争を起こしたときのこと、ユダヤ側の総司令官ヨセフスは、ヨタパタの町に籠城したが、ローマ軍に包囲され46日で陥落した。同志40人と洞穴に逃れたが食料も尽きてきた。衆議は降伏を拒否し自決することで決着したが、ヨセフスと彼の友人の2人は何とか生きのびたいと思っていた。いよいよ集団自決をする段になって、ヨセフスはある方法を提案した。それは、全員を円形に並べ、3番目に位置する者が他の同志に殺してもらい、これを繰り返す。最後の一人は自殺をするというものであった。この提案にみんなが賛成したので、ヨセフスと友人は16番目と31番目に位置して助かった。」

本記事のもくじはこちら：