2013年2月28日木曜日

継子立て

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

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

2013年2月26日火曜日

継子立て

わが家で塵劫記が, それも継子立てが話題になった. 私が小学生の頃持っていた本に塵劫記のことが書いてあり, 私は読んでいたから, 継子立ては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人の場合をシミュレートすべきであった.

2013年2月18日月曜日

Rubicキューブのシミュレータ

Winning WaysのRubicキューブの直し方(curing)が分ってきた. 実はその理解のために今回のシミュレータを書いたような次第だ.

島内本では6つの面をtop, north, east, south, west. bottomというが, 今回はWinning Ways流(というかDavid Singmaster流)にUp, Back, Right, Front, Left, Downとする.

各面の回転は時計まわりにU,B,R,F,L,D; 反時計まわりにはU',B',R',F',L',D'. またWinning Waysの説明には, 真ん中の段の回転もあり, それにはギリシア文字α,β,δ,γ,ε,ωを使う. εとωはeastとwestのようで覚えやすい.



このブログでは, 各小体の面を下の図の左のように表す.



右の図は操作の順で, まず下段の辺の2面体Aから始めEへとステージを進める.

A) Aの2面体を向きも合わせて定位置に置く.
B) Bの3面体を向きも合わせて定位置に置く.
C) Cの2面体を向きも合わせて定位置に置く.
D) Dの2面体を定位置に置く. 向きは気にしない.
E) Eの3面体を定位置に置く. 向きは気にしない.
F) Dの2面体とEの3面体の向きを合わせる.

Winning Waysではこれらの各ステージを

A) Aloft, Around (Adjust) and About.
B) Bottom Layer Corner Cubelets.
C) Central Layer Edge Cubelets.
D) Domiciling the Top Edge Cublets.
E) Exchanging Pairs of Top Corners.
F) Finishing Flips and Fiddles.

という.

ステージA) 下段は操作しにくいから, 上段のDの位置に集めてから各側面を回転してAに置く. Aのステージは簡単で, Aloft, Aroundなどはあまり関係ない.

ステージB) すでに置き終えたAの2面体に影響しないようにBの3面体を置く. 例えば面の図のpsの3面体(矢印の先)を置くには, それが上段にあればcnq の位置に来るように上段を回転し, 底の面の色がqにあればB1, nにあればB2, cにあればB3を実行する. 3面体が下段にあればいづれかの操作で上段に上げてから今の操作を行う.



図A) B1:F'U'F 底の面の色がqにあるとき
図B) B2:RUR'底の面の色がnにあるとき
図C) B3:F'UFRU2R' 底の面の色がcにあるとき

3面体が下段に移る他, orの2面体や上段のキューブにも影響があるが, そこは後で処理するので問題ではない.

ステージC) etかblにあるDの2面体をorのC(矢印の先)に移動する. 下段が揃っているから, 単純な面の回転は出来ない.



図D) C1:URU'R'U'F'UF oの色がUの面にあるとき
図E) C2:U'F'UFURU'R' rの色がUの面にあるとき

ここまでで下段と中段が揃う. この後は上段の2面体Dと3面体Eの入れ替えになる.

ステージD) 上段の2面体etとgを交換する.



図F) D1:UFRUR'U'F' 2面体bl, 3面体ai, cnq, hvも替わったように見えるが, これらは向きが替わっただけで, 位置は前のままである. 上段の2面体, 3面体の向きは最後のステージFで修正するから, 今は気にしない.

ステージE) 3面体cnqとhvを交換する(mono swapという).



図G) 1月22日のブログのG)巡回 で3面体aiがcnq, cnqがhv, hvがaiに移動している. これを3面体の交換2回でもとに戻す.
図H) 上段のT'の回転.
図I) E:FDF2D2F2D'F'=Msを実行. Hの赤丸と青丸の3面体を交換した. 中段と下段にも変化があるが, 上段はこの2つが変わっただけなのに注意.
図J) 上段のT'の回転.
図K) E=Msを実行. Jの赤丸と青丸の3面体を交換した. 上段の3つの3面体は希望の位置に移った. Ms2=1なので, 中段と下段がもとに戻ることに注意.

ステージF) 上段の3面体と2面体の向きを合わせる.

3面体の場合


図L) 1月22日のブログのH)ねじり で3面体cnqが時計回りに, hvが反時計回りにねじれている.
図M) F1=(F'RFR')2=Maで3面体cnqを反時計回りに回転する. 中段と下段にも変化があるが, 上段はこの3面体が回転しただけなのに注意.
図N) 上段のT'の回転.
図O) F2=(RF'R'F)2=Mcで時計回りに回転する. 中段と下段はMaMc=1で元に戻る. 後は上段をT回転する.

2面体の場合


図P) F)隣辺向き替え で2面体blとetの向きが反転している.
図Q) F2=(εR)4=Meでblを反転する.
図R) 上段をT'回転する.
図S) F2=Me を実行する. 中段と下段はMe2=1で元に戻る. 後は上段をT回転する.

この方法はMs2=1, MaMc=1, Me2=1をうまく利用していて面白い.

2013年2月4日月曜日

Rubicキューブのシミュレータ

シミュレータが出来たので島内先生の本の6面体完成術を実装することにした.

今回はその大体のやり方を書くことにしよう.

島内流にいうとRubicキューブには26個の小体があり, その内訳は隅にある3面体8個, 辺にある2面体12個, 面の中央にあり動かない1面体6個とである.

島内流の完成術は
A. 3面体を向きは無視して正規の位置に移す.
B. 2面体を向きは無視して正規の位置に移す.
C. 2面体の向きを揃える.
D. 3面体の向きを揃える.
である.

この各手順で主に使われるのが, 1月22日のブログにあった
E) 単純3角形 9a(Bで使う)
F) 隣辺向き替え24a(Cで使う)
G) 巡回 28a(Aで使う)
H) ねじり 33a(Dで使う)
の操作である.

まず6面の色を番号で表す.
上t 0(白)
北n 1(緑)
東e 2(橙)
南s 3(黄)
西w 4(赤)
下b 5(青)

隅(赤字で示す)と辺(青字で示す)も番号で表す.

3面体は正規の位置での3つの色を昇順に並べて表す. 隅番号0,1,2,...にある3面体は順に
[012],[023],[034],[014],[125],[235],[345],[145]

2面体は正規の位置での2つの色を昇順に並べて表す. 辺番号0,1,2,...にある2面体は順に
[01],[02],[03],[04],[12],[23],[34],[14],[15],[25],[35],[45]

現在 隅0にある3面体を知るには, 54の面の色のリストから0,15,18の位置の色をとりだし, 昇順にソートする. こうして8つの隅にどの3面体がいるかが分る.


[ランダムにした出発点]

Aの手順では, [012]を隅0に戻すことから始めて, 隅7まで戻すことである. 最初の頃は間単だ. たとえば[012]が隅番号n=0,1,2,3の何れかにあれば, 面tをnだけ左回転する. n=4,5,6,7なら面bをn-4だけ右回転し隅4に置き, 面eを左回転する.

[023]は隅2にいれば, 面sを右回転. 3にいればw右, s右だ. n=4,5,6,7なら(n+3)%4だけ右回転して隅5へ移し, sを左回転する.

このようにして上の4個はなんとかなる. 下の隅はまとめて対処する.

4つの3面体の相対位置により, 巡回 28aを1回か2回使うと, 正規の位置に収まる.


[3面体が元の位置にもどる]

次はBの手順で, 今度は隅に影響を与えないよう, 単純3角形 9aだけで対応する. これも辺0に[01]を移すのがもっとも楽で, 7になるとなかなか苦しい. 下の面の8,9,10,11は, Aの手順の最後のようにまとめて対応する. これも巡回を2回使うことで無事に完了する.


[2面体も元の位置に戻る]

Cの手順は隣の辺と一蓮託生なので, たとえば辺0の向きを変えると, 辺1,4,3,7のどれかも向きが変わる. それでせっかく揃っていた向きも壊れるかもしれない.

まず一筆描きの辺の順を決める. たとえば0,1,2,3,7,8,4,9,5,10,6,11とする. 辺0の2面体の向きが違っていたら, 0と1の辺の隣辺向き替えを行う. 次に辺1の2面体の向きを調べ, 違っていたら1と2の辺の隣辺向き替えを行う. このように順々に向き替えを続けるとこの手順は完了する.


[2面体の向きを揃える]

Dはねじりで, これは向きが揃うまで同じ操作を2回やらなければならないかもしれない. これも一筆描き, 0,1,2,3,7,6,5,4のように実行すれば 終わる.


[3面体も向きを揃える]

手順AやBの小体の移動に較べると, 向き替えははるかに簡単であった.

問題はそれぞれの操作がある位置についてしか書いてないことで, 人手で揃えるときはキューブをその向きになるよう持ち替えるのだが, 私はx,y,z軸について操作を回転した操作を生成するSchemeのプログラムを書き, あらゆる方向の操作を用意した上で好きな位置で処理が出来ようにした.

乱数を発生させてキューブをこねたあと, 元へ戻すプログラムを走らせると, 一瞬にして完成するのが感動的である. もちろん途中経過を出力しているから, 手順を追って完成させていることも確認できる.