進んで戻って

いよいよ年末が迫る. 元日からの通日は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+tC_s=_s+tC_t組が作れるわけだ.

その組合せを書き出すのに, 常識的には辞書式順, あるいは昇順に並べる. 次は(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個空きである. このパターンをA₃₃という. しかし, こういうパターンはこれだけでなく, 次のB₃₃もそうなっている.


途中には目をつぶると, A₃₃は111000から始まり, 011100で終る. B₃₃は111000から始まり, 001110で終る. 一般にA_stは, 0がs個, 1がt個から始まり, 0が1個, 1がt個, 0がs-1個で終り, B_stは, 0がs個, 1がt個から始まり, 0が2個, 1がt個, 0がs-2個で終る.

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

A_st = 1B_s(t-1), 0A_(s-1)t^R;
B_st = 1A_s(t-1), 0A_(s-1)t.

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



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

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

また, A₃₃ = 1B₃₂, 0A₂₃^R.

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

たしかに左の下半分のA₂₃と右の下半分のA₂₃^Rは, 上下が逆である.

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

これが最初の「一歩進む(A_st)には, 二歩進み(B_s(t-1)), 一歩戻る(A_(s-1)t^R). 二歩進む(B_st)には, 一歩進み(A_s(t-1)), もう一歩進む(A_(s-1)t)」の謎解きであった.

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