2010年12月26日日曜日

進んで戻って

いよいよ年末が迫る. 元日からの通日は360+αまで来た.

ずいぶん前になるが, 365歩のマーチという曲があり, その中に「3歩進んで2歩さがる」という文句があった. これを聞いて, 昼間に2メートル登り, 夜間に1メートル滑り落ちるカタツムリが, 地上から5メートルの電柱を登りきるのに何日かかるかというクイズを思い出す向きもあろう.

TAOCP V4F3に
"To take one step forward, take two steps forward, then one step backward; to take two steps forward, take one step forward, then another"
という禅問答のような記載があり, 私も直ぐには悟りえず, しばし悩んだことがある.

順列組合せと一緒にしていわれることが多いが, 組合せは, 0,1,...,n-1のn人から, s人を選ぶ方法のことである. これはn - s = t人を選ばない方法でもあるから, TAOCPでは(s,t)組合せという.

つまり, 0号室と1号室があり, 0号室の人数をs, 1号室の人数をtとする. 0番君からn-1番君のそれぞれが, どちらの号室にいるかを, nビットの二進数で表わす.

当然s+tCs=s+tCt組が作れるわけだ.

その組合せを書き出すのに, 常識的には辞書式順, あるいは昇順に並べる. 次は(3,3)組合せの例である.




この図の赤点は, 前後の組合せで異なる位置を示す. 二進数の位置を右から0,1,2,...とすると, 始めの方の最初の赤点は, 000111から001011になった時に, 2番君が1号室から0号室に, 3番君が0号室から1号室に移ったことを示す. 右下の最後の組合せの下に6つの赤点があるのは, 111000から最初の組合せ000111に戻るには, 全員が部屋を移る必要があるということである.

かくも大勢が右往左往しては, ドア回りが混雑するので, 回転ドア方式を考えた人がいる. 0号室と1号室の間に回転ドアがあり, 回転ドアを通って1人ずつだけが入れ替わるのである.



すなわち, この図で見るように, 赤点は常に2個である. なかなかうまく出来ている.

これは6ビットのGray codeを作り, 1のビットが3個のものだけリストして作った.

(define (gray bs)
(define (xor a b) (modulo (+ a b) 2))
(map xor bs (cons 0 (reverse (cdr (reverse bs))))))

(for-each (lambda (n) (for-each display n) (newline))
(filter (lambda (x) (= (apply + x) 3))
(map gray (map (lambda (n) (n2bs n 6)) (a2b 0 64)))))

ところでよく見ると, この赤点の間隔はいろいろだ. 2つ隣り同士のところが10, 間が1個空いているのが4, 2個空いているのが4, 3個空いているのが2で計20である.

この間の幅を0と1にしても出来るといい出した人がいるらしい.

がその1例である. 最後から最初に戻るのは別として, 途中の赤点はすべて隣り同士か1個空きである. このパターンをA33という. しかし, こういうパターンはこれだけでなく, 次のB33もそうなっている.


途中には目をつぶると, A33は111000から始まり, 011100で終る. B33は111000から始まり, 001110で終る. 一般にAstは, 0がs個, 1がt個から始まり, 0が1個, 1がt個, 0がs-1個で終り, Bstは, 0がs個, 1がt個から始まり, 0が2個, 1がt個, 0がs-2個で終る.

AとBの漸化式も知られている.

Ast = 1Bs(t-1), 0A(s-1)tR;
Bst = 1As(t-1), 0A(s-1)t.

これを図で示すと次のようになる. いまはs=t=3である.



左の組合せは, は下の黒文字の説明にあるように, B33である. 上の漸化式に当てはめると, B33 = 1A32, 0A23.

つまり, 左のB33は, A32の前に1を置いたものを並べ, 次にA23の前に0を置いたものを並べると読む. 1や0の後に置く部品の組合せは赤で囲んである. 説明も赤文字である.

また, A33 = 1B32, 0A23R.

つまり, 右のA33は, B32の前に1を置いたものを並べ, 次にA23の, 右肩にRがついているから, 上下逆転したものの前に0を置いたものを並べると読む.

たしかに左の下半分のA23と右の下半分のA23Rは, 上下が逆である.

改めて右のA33を見ると, 最初の111000は最後は011100になり, 111は右へ1歩進んだ. B33では, 111は右に2歩進んだ. 部品を見るとA32は11が右へ1歩進み, A23は111が右へ1歩進み, B32は11が右へ2歩進む. 右下のA23Rを上から下へ眺めると, 今度は01110が11100になるから, 111が1歩戻ったことになる.

これが最初の「一歩進む(Ast)には, 二歩進み(Bs(t-1)), 一歩戻る(A(s-1)tR). 二歩進む(Bst)には, 一歩進み(As(t-1)), もう一歩進む(A(s-1)t)」の謎解きであった.

私がこの解釈に気づいたのは, 2008年の1月頃であった, 2008年の夏にKnuth先生に会った時, 「あの2歩前進, 1歩後退の意味は, 苦労したがついに分かった.」と報告した. Knuth先生は笑っただけであった.

2010年12月25日土曜日

微分解析機

今回は微分解析機といっても, トルクアンプ, 日本語では回転力増幅器の, それも図の話である.

微分解析機の積分機の出力は, 摩擦で生じる微少な力なので, これで他のものを駆動することは出来ない. ところがNewmanにより, トルクアンプが発明され, それによって微分解析機は実用になった.

トルクアンプは, 下の図のような構造である.



右のinputの軸の回転を, 左のoutputの軸から力を増幅して取り出すのである. その間にロープを書けたドラムが2組あり, ロープの端は, 入力と出力軸に取りつけたT字状のレバーの先に固定されている. ドラムは両端のプーリーにかけたベルトで, 矢印の方向に, 逆方向に回転している. 入力軸が回転しない時は, ロープはドラムの面を滑っている.

今, 入力軸が, 右に回転したとする. そうすると, 下のT字状のレバーが持ち上がり, 左のロープがドラムの上で締まり, ドラムとの間に摩擦が生じ, 上のT字状のレバーが押し下げられ, 出力軸が入力軸と同じ方向に回転する. 回転角が同じになれば, ロープは弛み, 再び滑り出す.

入力軸が反対に回る場合は, 右のドラムの摩擦が生じ, 出力軸はやはり入力軸と同回転する.

つまり, 回転するドラムが動力になり, 入力の微少な力を増幅するのである.

こういう仕掛けは船の碇を巻き上げる装置にもあるらしい.

さて, 上のような図で説明したが, 私としては, ロープを直線で描いたのが気に入らないのである. 図はなるべく正確に描きたいというからには, このようにドラムの縁で光の反射のような図はだめである.



そこで考えたのがこの図である. 上と下のT字状のレバーにロープが繋がっている点をAとEとする. 図の円はドラムの断面である. ロープは, AからBに至ってドラムに接し, BCDFBCDとドラムを1回とすこし回り, Dから離れてEでもう一方のT字状のレバーに辿り着く. 先ほどの図は, これを左から見たものだ. そうすると, ロープ上の点は, Aから下がり, ドラムの円の右半分を上がり, また下がるように見えるはずである. また左右の座標位置は, ロープの長さに比例して右へ移動するはずである.

その移動の様子を, 半径の右の, 点の列で示す. 赤はロープのAからBに対応する. 緑はBCDFBCDに対応, 最後の青はDからEである.

そういう解釈で, 最初の図を描き直すと下の絵になる.



ざっと見ると最初の図と左程違わないが, ドラム回りのロープは本当らしくなったのではないか.

2010年12月23日木曜日

クリスマスツリー講義

今月(2010年12月)始め, Knuth先生から, いつもの航空便ではなく, 珍しくメイルで返事が来た. その最後に

By the way, my lecture next Monday will probably be webcast live, so you might be able to watch it via Internet in Japan.

と書いてあった. その日(日本時間では7日朝)は所用あって, インターネットも見ずに過ぎたが, ホームページには,

Monday, 06 December, 5:30pm, in the new NVIDIA auditorium (Huang Engineering Center) A Computer Musing entitled ``Why pi?'' [the sixteenth annual Christmas Tree Lecture]

あ, これがあのクリスマスツリー講義(Christmas Tree Lecture)だったのか.

すぐに連想するのは, 元祖「クリスマス講演」である.

「これから皆さんにロウソクのお話をいたそうと思います.」で始まるMichael Faradayの「ロウソクの科学」は, 1860年のクリスマスであった. だから150年前の話だ. ところでこの原題はThe Chemical History of a Candleという.

Royal Institution Christmas LecturesをWikipediaでみると, 1825年に始まり, 第2次世界大戦中を除き, 今年も続けているというから, 英国のこだわりにはまったく脱帽する.

一方, クリスマスツリー講義は, Knuth先生が, 年末に一般向けに講義するものらしい.

TAOCP V4F4の表4に8次のクリスマスツリーパターンという図があり, その脚注に(TAOCPに脚注があるのは異例なことだが),

"This name was chosen for sentimental reasons, because the pattern has a general shape not unlike that of a festive tree, and because it was the subject of the author's ninth annual "Christman Tree Lecture" at Stanford University in December 2002."

と書いてある.

8次は大きすぎるから遠慮し, 6次のクリスマスツリーは以下のように, 6ビットの二進数64個を, 6C3=20行, 6+1列に配置する.

左からの各列は, 1の個数が0, 1, ..., 6である. 従って中央の高さは6C3である. 同じ行では, 右に行くに従い, 0が1に変っていく. 赤い0は, 次に1になるもの, 青い1は, 前に0だったものだ.

この配置法は, 1951年にde Bruijn, van Ebbenhorst Tengbergen, Kruyswijkが発見した.



101010
101000 101001 101011
101100
100100 100101 101101
100010 100110 101110
100000 100001 100011 100111 101111
110010
110000 110001 110011
110100
010100 010101 110101
010010 010110 110110
010000 010001 010011 010111 110111
111000
011000 011001 111001
001010 011010 111010
001000 001001 001011 011011 111011
001100 011100 111100
000100 000101 001101 011101 111101
000010 000110 001110 011110 111110
000000 000001 000011 000111 001111 011111 111111


これはどうできているかというと, 1次は

0 1

の1行. これではクリスマスツリーにならない. 2次は

10
00 10 11

の2行. いささかツリーらしくなる.

さて, n次のツリーの各行を,
σ1,...,σs
とすると, n+1次のツリーは, 各行を
σ20,...,σs0と
σ10,σ11,...,σs1の
2行にする.

すなわち, 後に0をつけたものと, 後に1をつけたものを作り, 0をつけたものの先頭の1個を1をつけたものの先頭に移動するのである. 先頭を外した後が0個になったら, その行は除く.

Schemeで書くと

(define (next ct)
(if (null? ct) '()
(let ((ss0 (map (lambda (s) (string-append s "0"))
        (car ct)))
(ss1 (map (lambda (s) (string-append s "1"))
        (car ct))))
(set! ss1 (cons (car ss0) ss1))
(set! ss0 (cdr ss0))
(if (null? ss0) (cons ss1 (next (cdr ct)))
(cons ss0 (cons ss1 (next (cdr ct))))))))

である. ctを

(define ct '(("0" "1")))

によって1次のクリスマスツリーとし, ctにnextを順に作用させると,

(("10") ("00" "01" "11"))

(("100" "101") ("010" "110") ("000" "001" "011" "111"))

(("1010") ("1000" "1001" "1011") ("1100")
 ("0100" "0101" "1101") ("0010" "0110" "1110")
("0000" "0001" "0011" "0111" "1111"))


が得られる. クリスマスツリーらしいのは, 次数nが偶数の時である.

6次のクリスマスツリーパターンは, 異なる64の要素があるから, それを八卦の64のパターンで置き換えたのか以下である.



これは, 昨年の, 私からKnuth先生へのクリスマスカードであった.

2010年12月22日水曜日

1のかたまり

TAOCPに  Ank=0n n-kC2k  という式があった(演習問題7.1.4--125).

その解答のHistorical Noteに Ancounts binary x1...xn-1 with each 1 next to another と書いてある. なんだろうと思っているうちに, Knuth先生からのある手紙にヒントがあった.

ちなみにAnの値は

n 1 2 3 4 5 6 7 8 9 ...
An 1 1 2 4 7 12 21 37 65 ... .

とりあえずn=5を考える. するとbinary x1...xn-1

0 0 0 0 *
0 0 0 1
0 0 1 0
0 0 1 1 *
0 1 0 0
0 1 0 1
0 1 1 0 *
0 1 1 1 *
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0 *
1 1 0 1
1 1 1 0 *
1 1 1 1 *


with each 1 next to another は, 1があれば単独では現れないということで, そういうものは, 上で星印をつけた7=A5個になる. 1は孤立していて失格である. 問題はこのパターンの見つけかたである. 星印のものを取り出すと

0 0 0 0
0 0 1 1
0 1 1 0
0 1 1 1
1 1 0 0
1 1 1 0
1 1 1 1

最初のは1がないから別にして, 残りは1のかたまりが1個ある. 1が孤立するかたまりはないから, 1のかたまりから1個外したパターンを書くと

1 2 3 4
0 0 1
0 1 0
0 1 1
1 0 0
1 1 0
1 1 1

となる. ビットの境界に左から1,2,3,4と番号をつけ, 0と1の境界の位置を書いてみると

3 4
2 3
2 4
1 2
1 3
1 4

となり, これは4個から2個選ぶ数であった. つまり4C2=n-1C2=6.


同様にして, 1のかたまりが2個あるパターンは, n=7の0 1 1 0 1 1 から考え始めて

1 2 3 4 5
0 1 0 1 2 3 4 5
1 0 0 1 1 2 4 5
1 0 1 0 1 2 3 4
1 0 1 1 1 2 3 5
1 1 0 1 1 3 4 5

だから, 右にあるような境界の位置を見れば, 5C4=n-2C4(1のかたまりが2個の場合).

という次第で, 一般に1のかたまりがk個ある数はn-kC2k.
一番上の1のかたまりのないものはnC0=1.



2項係数nCmは, n<mの時に0だから, かたまりがとれるところまで足せばよく, 1のかたまりの置き方の数になるのであった. 結構むずかしい. 私もヒントなしでは, ここまで辿りつかなかっただろう.

2010年12月11日土曜日

2011

1年ほど前 2010が1から9までを使ったどういう式で表わせるかを計算し, このブログに書いたことがある.

今回は2011である. 28個の解があった.


(+ 1 (* (/ 2 3) (- (* (* (* (+ 4 5) 6) 7) 8) 9)))
(- 1 (* 2 (+ 3 (* (* (- (- (- 4 5) 6) 7) 8) 9))))
(- (* (- (/ 1 2) (* (* (- (- 3 4) 5) 6) 7)) 8) 9)
(+ (* 1 2) (* (+ 3 4) (- (* (+ (* 5 6) 7) 8) 9)))
(* 1 (+ 2 (* (+ 3 4) (- (* (+ (* 5 6) 7) 8) 9))))
(* 1 (- (* (+ (* 2 3) 4) (- (* (* 5 6) 7) 8)) 9))
(- (* (+ (+ (+ 1 2) 3) 4) (- (* (* 5 6) 7) 8)) 9)
(- (* (+ (* (* 1 2) 3) 4) (- (* (* 5 6) 7) 8)) 9)
(- (* (* 1 (+ (* 2 3) 4)) (- (* (* 5 6) 7) 8)) 9)
(- 1 (* (/ 2 3) (- (+ 4 5) (* (* (* 6 7) 8) 9))))
(+ 1 (* (* (/ 2 3) (+ (- 4 5) (* (* 6 7) 8))) 9))
(+ (- (* 1 2) 3) (* 4 (+ (- 5 6) (* (* 7 8) 9))))
(* 1 (+ (- 2 3) (* 4 (+ (- 5 6) (* (* 7 8) 9)))))
(+ (* 1 (- 2 3)) (* 4 (+ (- 5 6) (* (* 7 8) 9))))
(+ (/ 1 (- 2 3)) (* 4 (+ (- 5 6) (* (* 7 8) 9))))
(+ 1 (* (+ 2 (* (- 3 (* 4 (- (/ 5 6) 7))) 8)) 9))
(+ (* 1 2) (* (+ 3 4) (+ 5 (* 6 (- (* 7 8) 9)))))
(* 1 (+ 2 (* (+ 3 4) (+ 5 (* 6 (- (* 7 8) 9))))))
(- (- 1 (* 2 3)) (* (* (* (* 4 (- 5 6)) 7) 8) 9))
(- (- 1 (* 2 3)) (* (* (* (/ 4 (- 5 6)) 7) 8) 9))
(- 1 (* (+ (/ 2 3) (* (* (* 4 (- 5 6)) 7) 8)) 9))
(- 1 (* (+ (/ 2 3) (* (* (/ 4 (- 5 6)) 7) 8)) 9))
(- (* 1 2) (* (+ 3 4) (+ (* (- 5 (* 6 7)) 8) 9)))
(* 1 (- 2 (* (+ 3 4) (+ (* (- 5 (* 6 7)) 8) 9))))
(- 1 (* (* 2 3) (+ (* (- (- 4 5) (* 6 7)) 8) 9)))
(+ 1 (* (* 2 3) (- (* 4 (+ (* 5 6) (* 7 8))) 9)))
(- 1 (* (* (- (/ 2 3) 4) (+ (+ 5 6) (* 7 8))) 9))
(+ (* (+ 1 (* (* 2 (+ 3 (* 4 5))) 6)) 7) (* 8 9))


最後の
(1+2*(3+4*5)*6)*7+8*9
が美しい.