パズルの国のアリス

ハートの女王による継子立て(問題)

坂井 公(筑波大学) 題字・イラスト:斉藤重之

 表敬訪問の際の歓待のお礼として,鏡の国のチェス王室秘蔵の「不老不死薬」が不思議の国のトランプ王室へ贈られてきた。1人しか使えないということもあって,兵士たちの誰かに特別ボーナスとして支給しようということになり,トランプ城の中は誰がもらうかで騒ぎになっている。

 アリスが見たところ,トランプ城の住人たちは「老」にも「死」にもあんまり縁がなさそうで,そんな薬の何がありがたいのかわからないのだが,どうやら兵士たちはもらえるものは何でももらおうというつもりらしい。

 王室がどうやって人選をするのだろうかと,アリスが見学に行ってみると,ハートの女王は兵士全員をホールに集め,スペード,ハート,クラブ,ダイヤの順にエースから10まで輪になって並ぶように言った。それからアリスに「そちの好きな数は何か」と訊き,アリスが「7です」と答えると,スペードのAから順に1から7までの番号を繰り返し唱えさせ,7を唱えたものを次々に輪から外していった。最後まで残った者に景品を支給するつもりらしい。

 何のことはない。「継子立て」で知られる問題である。ヨーロッパではヨゼフス問題と呼ばれることが多い。馴染みのある読者も多かろうが,今月はこのパズルを少し楽しんでいただこう。まずは,ウォーミングアップ問題として,この女王による継子立ての結果,「不老不死薬」を手に入れた兵士は誰かを考えてほしい。また,もしアリスが41人目として,この継子立てに加わることが許され,自分の位置を選べるとしたら,景品を入手するには,どの兵士の間に入るのがよいだろうか?

 この2つのウォーミングアップ問題は,地道にやれば必ず正解が得られるが,次に,アリスが比較的小さな数を選んだ場合に,この計算を高速化する方法を考えてほしい。例えば,アリスが選んだのが7でなく2,3,4の場合,誰に景品がわたるかを早く決定する方法はあるだろうか?

 最後の問題としては,好きな数を聞かれたのがアリスでなく,兵士の1人だったとして,自分が景品を手に入れられるようにその数を選ぶ方法を考えてほしい。

解答はこちらです