継子立て

Concrete MathematicsのJosephusの問題のところにこういう演習問題があった.

最初に善玉n人を並べ, 次に悪玉n人を並べて2n人の円形にし, m人ごとに除外すると, 最初に悪玉が全部除外されるような, nに依存したmが存在することを示せ.

例えばn=3ならm=5, n=4ならm=30とできる.

Suppose there are 2n people in a circle; the first n are "good guys" and the last n are "bad guys." Show that there is always an integer m (depending on n) such taht, if we go around the circle executing every mth people, all the bad guys are first to go? (For example, when n=3, we can take m=5; when n=4, we can take m=30.)

n=3,m=5でやってみると,

位置の0,1,2が善玉で, 3,4,5が悪玉なので, 位置4,3,5の順に除外され, たしかにそうなる.

計算機の威を借りてさらにmを探すと
n=3 (5 52 60 65 112 120 125 172 180 185 232 240 245 292 ...)
n=4 (30 71 101 175 205 216 246 320 350 391 421 ...)
n=5 (169 217 330 378 979 ...)

Answerを見ると

m be the least (or any) common multiple of 2n, 2n-1, ..., n+1.

n=3のとき, 上の図では, 2nごとに位置5のところへ回ってくるから, 2nの倍数で5が除外され, 人数が1人減るから次は2n-1の倍数で4が除外され, 最後n+1の倍数で3が除外される.

n=3のときはlcm(6,5,4)=60だからm=60,120,180,... m=5はその方法とは違って偶然うまくいく場合だったらしい. 65,125,185もその流れの解である.

n=4だとlcm(8,7,6,5)=840. n=5だとlcmは2520になる.

nから計算でmは得られるのが分かったが, 問題の例に偶然見つかる方を書くのはどうかなぁ.

ところでConcrete Mathematicsの訳書で, この問題は「2n人が環状に並んでいるとする. 半分のn人は「よい人間」で, 残りのn人は「わるい人間」だとする.」と始まる.

この記述では善悪それぞれn人ずつが固まっているとは読めない. 継子立てのように, 30人が環状に入り交って並び, その半分の15人が先妻の子で, 残りの15人が後妻の子であるのと同様に読めてしまう.

私は原書の方を読んでやっと問題の意味が理解できた. もう少し慎重に翻訳して欲しい. (ここを訳したのは誰だ.)

継子立て

わが家で塵劫記が, それも継子立てが話題になった. 私が小学生の頃持っていた本に塵劫記のことが書いてあり, 私は読んでいたから, 継子立ては70年来のお馴染みである.

Concrete MathematicsやMathWorldによると外国ではJosephusの問題というらしい.

概要はこうだ. 先妻の子15人, 後妻の子15人がいる. 後妻はその中から1人選ぶのを自分の子にしたい.

15人ずつの先妻の子, 後妻の子をある順に円形に並ばせ, 出発の位置から順に数えて10人目ごとに除外する.

次の図の外側の円がそれだ. 円周の内側の黒の数字が位置で, 真上の0から時計回り1,2,...,29まで続く. 円周上の小円内の数字が赤のところには後妻の子を, 黒のところには先妻の子を置く.

小円の中の数字は除外される順を示す. 真上の0から時計廻りに数えると10人目は位置9だ. これが最初なので小円には0を記す. 位置9の子を除外し, その次から数えると10人目は位置19 になる. 小円には1を記し, それも除外し,... を続けると, 小円内の14までが黒なので, (不思議にではないが)先妻の子ばかり14人除外される.



先妻の子の15人目が除外されそうになると, その子は, 次は自分から始めてほしいと訴え, 内側の円のように再開する. 今度は不思議に後妻の子ばかり除外され, 最後に真上の先妻の子0 が残るという話だ.

後妻が子の配置を決めるのは簡単である. 外側のような図を書いてシミュレーションし, 15番目に除外される場所までを先妻の子にすればよい.

しかしコンピュータ屋のわれわれが手でシミュレーションするのは業腹だ. やはりプログラムを書こう.

lispでは円形のリストが作れる.

たとえば

(define foo '(0 1 2 3))
(set-cdr! (list-tail foo 3) foo)

で
位置 0 1 2 3 4 5 6 7 8 9 a b ..
要素(0 1 2 3 0 1 2 3 0 1 2 3 ..)
の無限リストfooができる.

このようにして30人のリストhead (0 1 2 ... 29)を作り, set-cdr!で円形, 無限にする. 10番目, つまり0から数えれば9番目の要素を除外するには

(set-cdr! (list-tail head 8) (list-ref head 10))

で9の両側のリンクが繋がる. これでheadは9の抜けた

(0 1 2 3 4 5 6 7 8 10 11 12 ...)

になる. そうしてheadを9進める.

(set! head (list-tail head 9))

この様子は次の図の左のようだ. headはnextの位置に進む.



しかし円を構成するメンバーの数が少なくなると, これでは失敗する. 上の図の右を見て欲しい. headから0,1,...,と進むと9番はremoveと書いてある1になる. 従ってその両端を繋ぐ. headをnextのところに進めたいが, 9先は0,2,3,4,5,6,7,0,2,3と進んでnext'と書いた3になる.

この失敗をしないためには, 除外する前に10進んでnextの位置を先に確保することだ. そうして書いたプログラムが次だ.

(define (exclude)
(let ((next (list-tail foo 10)))
(set! bar (cons (list-ref foo 9) bar))
(set-cdr! (list-tail foo 8) next)
(set! foo next))
(display bar)
(display (map (lambda (n) (list-ref foo n)) (a2b 0 16))) (newline)
'ok)

後妻も16人の場合をシミュレートすべきであった.