継子立て

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人が後妻の子であるのと同様に読めてしまう.

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