三角錐の体積

今月初めにあった埼玉県公立高校入試問題が新聞に出ていた.

その中にこういう数学の問題がある.

右の図は, 三角錐の展開図です. △ABCはAB=16cm, BC=8cm, ∠ABC=90°の直角三角形です. また, 点D, Eは, それぞれ辺AB, ACの中点であり, 点Fは, 線分DBの中点です. このとき, 線分DE, EF, FCを折り曲げてできる三角錐の体積を求めなさい.



面白そうだ. これはちょっとやってみようと思いつつものびのびになっていた.

まずは正攻法.



Dの辺りを原点とし, DとBが合わさった頂点をP, その座標をx,y,zとする. 三角錐の底面の頂点E,F,Cからの稜の長さも図に示す通りだから, 式が書ける.

x²+(4-y)²+z²=4²
(4-x)²+y²+z²=4²
(8-x)²+(8-y)²+z²=8²

x=yなのは初めから分る. 解くとx=y=z=8/3が得られ, 底面の△EFC=24(cm²)だから体積は64/3(cm³).

思いのほか簡単な数値であった. ところで待てよと思う. なるほど∠Bと∠ADEが直角なので, EFPの面に対して稜PCは垂線になるわけだ. こちらの三角錐で計算すれば, 底面積は8(cm²), 高さは8(cm)なので暗算で計算できる問題であった.

スマートエイジング

3月6日から8日まで, 東北大学川内キャンパスで, 情報処理学会の第75回全国大会が開催された.

招待講演のひとつが, 東北大学加齢医学研究所の川島隆太教授の「スマート・エイジング〜脳機能解析学が拓く新しい超高齢社会〜」であった.

高齢者のひとりとして聞かざるを得ない話題である.

高齢期には
□脳を積極的に使う
□身体を積極的に動かす
□バランスのとれた栄養を摂る
□社会や他者と積極的に関わる
が肝心であるとのご高説であった.

脳を積極的に使うには, いわゆる脳トレが不可欠で, ふたつのデモがあった.

ひとつは「スパン課題」で, 次のような画面で9個の黒い丸がランダムに一瞬だけ色が変る. その順番を覚えておくものである.



もうひとつは「Nバック課題」で, 簡単な加算の問題が次々と現れる. それをN個あとに答えるものである. つまり計算の結果を長さNのシフトレジスタにいれ, 出口側から出る数を答えるのである.

これらの脳トレ課題は, 任天堂から発売されているそうだが, 私としてはProcessingでプログラムを書きたい衝動に駆られた.

仙台からの帰途は, 金曜の晩だけあって, 自由席を指定席に変える列が長大で, 並んでいる内に指定席がなくなるような状態であった.

止むをえず, やまびこの自由席で帰ることにしたが, 私の好きなE2系の1000番台で仙台始発. 缶ビールを飲みながら, 早速「スパン課題」のプログラムに 着手した. 最初のバージョンは列車が大宮に着くずっと前に完成した. 簡単であった.

今日はそれに機能を追加した. 画面の下方の6から15は1回の試行に色の変る回数である. 6をクリックすると6回色が変わり, 変わった位地が画面の下に表示される. 位置は最上段の左から0,1,2. 中段は左から3,4,5. 最下段は左から6,7,8である.



画面の右に見えるスライドバーは, 下端にあるときは, 色の替わる周期が2分ごとで, 上端では30秒ごとになる.

脳トレに興味があれば, ここに置いてあるので, 使ってみてほしい.

「Nバック課題」はそのうち書いて見よう.

継子立て

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人の場合をシミュレートすべきであった.

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'UFRU²R' 底の面の色が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:FDF²D²F²D'F'=M_sを実行. Hの赤丸と青丸の3面体を交換した. 中段と下段にも変化があるが, 上段はこの2つが変わっただけなのに注意.
図J) 上段のT'の回転.
図K) E=M_sを実行. Jの赤丸と青丸の3面体を交換した. 上段の3つの3面体は希望の位置に移った. M_s²=1なので, 中段と下段がもとに戻ることに注意.

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

3面体の場合


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

2面体の場合


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

この方法はM_s²=1, M_aM_c=1, M_e²=1をうまく利用していて面白い.

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のプログラムを書き, あらゆる方向の操作を用意した上で好きな位置で処理が出来ようにした.

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

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

Rubicキューブのどの面をどう回せといわれても, 手でやっていれば, 手順が複雑になってくるとつい間違えてしまうのは誰にも経験があろう.

その点, シミュレータはプログラムをしっかり書けば何回でも正しく処理できる.

Winning WaysにはElena Conwayが好んだパターンを作る手順が書いてある. どんなパターンか興味があったが, シミュレータを使えばそのパターンを作るのは簡単であった.

Aは4 Windows. Bは6 Windows. CはChequers. DはHarlequin. EはStripey. FはZigzag. Gは4 Crosses. Hは6 Crossesというらしい.

手順は省略する. Winning Ways, Vol. 4, p. 876参照.