東大 98 年後期 3(2)

数学

入試数学で過去最難問とか言われてるとnuc さんとこに書いてあったのでやってみた。(問題文は link 先とか Google 先生にもらってください。) 噂通り難しい…何度も中断するハメになったので正確にはわからないけど、たっぷり 10 時間は使ったと思う。その後、河合塾の解答例を見たら同じ方針だったけど、河合の解答は一番肝心な所 (白から到達可能と黒から到達可能は排反) の証明をしてなかったので、吹いてしまった。
なお、この blog にもっと美しい解法が載っている。こういうセンスのいい証明がサラリとできるようになりたい。Link 先の解法は、白だらけの可能グラフの各ノードに UID を振ってそれぞれが誕生した瞬間を分析すればいいですよというお話。その際、問題の形を一元化するために両端にノードを補完しているのが見所。
でも、河合の解答を補完したものはパッと見、見当たらなかったし、白からの操作と黒からの操作が本当に排反か疑ってるコメントもあったので、一応自分の解答を晒しておく。ちなみに間違いを見つけた方はご一報ください。

2010/08/26 補題 2 の証明をちょっと修正。
2010/10/03 補題 3 の証明を若干簡略化。

定義・表記規則

まず、表記上の利便性のためビット列の問題に置き換える。棒状グラフのノードの色を、適当に選んだ端から順に白なら 0 黒なら 1 として色を書いていく事で表す。例えば白黒黒は 011、ただし通常のビット列と違って鏡像関係のもの同士は等しい: 例えば 011 = 110。特に断らない限り a, b, c, d, e は 1 ビット、s, t, u, v, w, x, y, z は長さ 0 以上のビット列とする。

操作 1 と 2 はビット列の任意の場所に 0 を挿入して両隣 (端の場合は存在する方の隣) のビットを反転するという操作に一元化できる。(操作 1 は次数を上げてしまうので、棒状グラフを作るときには端にしか使えない。) この操作を展開と呼び、一回 s を展開することで t が得られる場合、s >> t と書く。また、これとは別に 0 をどこかから消して両隣 (端ならry) を反転させる操作を簡約と呼び、s を一回簡約して t が得られるなら s → t と書く。0 回以上の展開または簡約は s >>* t や s →* t のように書く。簡約は展開の逆操作なので、s → t は t >> s と同値であることに留意。\underline{s} を s のビットを全て反転したものとし、n 回反転する時は \underline{s}_n のように書く。はてなでこうやって書くと高さがずれるなあ。まあいいや。同じビット列の繰り返しは s^n のように書く。空の (長さが 0 の) ビット列を \varepsilon とする。

ビット列 x に対し、x] は x の右端 (存在すれば) を反転したもの、[x は左端を反転したもの、[x] は [x に ] を適用したものとする。ただし x = \varepsilon のとき、これらはいずれも \varepsilon になる。なお、[x] は x] に [ を適用したものと一致することに注意。

解法

問題の答えは、「n が 3 で割ってあまり 0 か 1 であることが必要十分」。まず十分は簡単。0 から始めて 000 が容易に作れ、それらをごにょごにょすれば白を 3 つづつ増やせるから、0^{3i} と 0^{3i+1} は全て可能。ところで 1 から始めると 00 が簡単に作れるので、(\forall i \geq 0)\,1 \gg^* 0^{3i+2}。よって、1 \gg^* u と 0 \gg^* u が排反であると証明すれば必要が示せる。これは u \rightarrow^* 1 と u \rightarrow^* 0 が排反であることと同値であるから、そちらを示す。

補題 1: s \rightarrow^* 1^n で s\neq 1^n ならば s \rightarrow^* \underline{0}_n。

証明: n について帰納。n=1 なら自明。n ≧ 2 のとき、s \neq 1^n より (\exists u)\,s\rightarrow^* u\rightarrow 1^n。すると 1^n \gg u なので、u は 1^{n-1}00 (端に 0 を挿入した場合) と 1^{n-k}0001^k の形に限られる。ただし後者は n ≧ 3 に限り、0 ≦ k ≦ n。1^{n-1}00 は右から 2 番目の 0 を繰り返し簡約で消すと 1^{n-1}00 \rightarrow^* 0\underline{0}_{n-1} \rightarrow \underline{0}_n。1^{n-k}0001^k は一番右の 0 を消していくと 1^{n-k}0001^k \rightarrow^* 1^{n-k}0\underline{0}_k0 \rightarrow 1^{n-k}0\underline{0}_{k+1} で、今度は一番左の 0 を消していくと \underline{0}_{n+2}\,(= \underline{0}_n) になる。\qed

補題 2: x\neq \varepsilon のとき、何らかの n ≧ 0 について次のいずれかが成立する。

(i) (\forall s, b, t, c) sbx \rightarrow^* sb01^n \wedge tc[x \rightarrow^* tc1^{n+1}
(ii)(\forall s, b, t, c) sbx \rightarrow^* sb1^{n+1} \wedge tc[x \rightarrow^* tc01^n
なお、対称性により、左右を反転してもこの補題は成立する。
証明: x は空でないので x = dx' と置ける。x' を含む全てのビット列は 0 か 1^n の形に簡約できるが、この簡約を d の右で再現すると、副作用として d が何回か反転する。x' の簡約先が 0 なら、もう一度簡約することで 1^n (n=0) となる。そうして x' を簡約しきった後に残る d の成れの果てを d' とすると sbx \rightarrow^* sbd'1^n \wedge tc[x \rightarrow^* tc\underline{d'}1^n。ここで d' = 0 なら (i) が、d' = 1 なら (ii) が成立する。\qed

で、本題。ここからは場合分けと細かいミスの機会の嵐。

補題 3: u \rightarrow^* 0 と u\rightarrow^* 1 は排反。

証明: u の長さ |u| について帰納。|u| = 1, 2 なら自明。|u| ≧ 3 のとき、仮に u が 0 にも 1 にも簡約できるとし、矛盾を示す。u \rightarrow^* 0 は |u|-1 ≧ 2 回の簡約を含むので、(\exists v)\,u \rightarrow v \rightarrow^* 0。しかし帰納的仮定により v \not\rightarrow^* 1 であるから、(\exists w \neq v)\, u \rightarrow w \rightarrow^* 1。簡約の結果は消すビットの位置だけで決まるので、u は二つ以上 0 を含まなくてはならず、u = x0y0z となる x, y, z が存在し、v = x][(y0)z で w = x(0y)]z。(注: y は空の可能性があり、] や [ が y を突き抜けて隣の 0 を反転するかもしれないので、(0y), (y0) と 0 を括弧でくくり込んだものに適用している。)

ここで、v →* s ←* w なる s が存在する事を示せば、帰納的仮定と矛盾する事に注目しておく。なぜならば、もし s が 0 を含むならば補題 1 により s →* 0 または s →* 1 が成立し、v も w も同じものに簡約できてしまう。もし s が 1^n の形ならば、s ≠ v, w である (v, w はそれぞれ 0, 1 に簡約出来てかつ長さ > 1 なので 0 を必ず含む)。したがって、やはり補題 1 により v も w も同じ \underline{0}_n に簡約できてしまう。

y \neq \varepsilon のとき、v = x][y0z で w = x0y][z で、それぞれ残った 0 を簡約で消すといずれも x][y][z になるので、s = x][y][z とおけば上記の理由により矛盾が導ける。

y = \varepsilon のとき、u = x00z、v = x]1z, w = x1[z である。ここで、|v|=|w| ≧ 2 である事より、x, z のうち最低一つは空であってはならない事に注意しつつ、場合分けする。

(i) x = \varepsilon, z \neq \varepsilon の場合。z = bz' とおけて、補題 2 より 1bz', 1\underline{b}z' \rightarrow^* 1^{n+2}, 101^n (順不同) となる。v も w も 0 か 1 まで簡約出来るので、いずれも 1^{n+2} に等しい事はありえない。したがって 1^{n+2} に簡約できる方は補題 1 より \underline{0}_{n+2} に簡約できる。一方、101^n に簡約できる方はそのまま左から二番目のビット位置にある 0 を繰り返し消すことで \underline{1}_{n+1} = \underline{0}_{n+2} に簡約できてしまう。矛盾。

(ii) x \neq \varepsilon, z = \varepsilon の場合。(i) と同様。

(iii) x \neq \varepsilon, z \neq \varepsilon の場合。補題 2 を適用した結果によりさらに場合分け。

(a) x]1z \rightarrow^* 1^n01z \wedge x1[z \rightarrow^* 1^{n+2}[z の場合、さらに補題 2 を適用して二つの場合に分かれる。

(a.I) 1^n01z] \rightarrow^* 1^n0101^m \wedge 1^{n+2}[z \rightarrow^* 1^{n+m+3}の場合。1^n0101^m \rightarrow^* \underline{1}_{n+1}01^m \rightarrow^* \underline{1}_{n+m+1} = \underline{1}_{n+m+3} なので矛(ry

(a.II) 1^n01z \rightarrow^* 1^n01^{m+1} \wedge 1^{n+2}[z \rightarrow^* 1^{n+2}01^m の場合。x の右端のビット (存在すれば) を k 回反転したものを x]^k と書くことにすると、1^n]01^{m+1} \rightarrow 1^n]01^m \rightarrow 1^n]^m0 と 1^{n+2}01^m \rightarrow^* 1^{n+2}]^m0 が成立する。そしてまた m の偶奇で場合分け…ごめんこれで最後

(a.II.E) m が偶数なら (\forall x)\,x]^m = x となり、1^{n+2}]^m0 = 1^{n+2}0 \rightarrow^* 1^n0 = 1^n]^m0 が成り立つ。よって (ry

(a.II.O) m が奇数なら (\forall x)\,x]^m = x] となり、1^{n+2}]^m0 = 1^n100 \rightarrow^* 1^n01 \rightarrow 1^n]0 = 1^n]^m0 (ry

(b) x]1z \rightarrow^* 1^{n+2}z \wedge x1[z \rightarrow^* 1^n01[z の場合。(a) と同様。\qed

感想

長っ… 多分こんなん間違わないように書くだけで時間配分をオーバーします。しかも「〜を繰り返し」で帰納的証明いくつか省略してるし高校ではありえなさ気味な論証使ってるし。もうちょっと場合分けを減らせればなんとかなる…か…? 何か途中で ] と [ を高階関数として定義すれば何とかなりそうな気がしたけど、どうすればいいかよくわからんかった。

ちなみに、簡約が confluent になったら面白いな〜とか考えてたらこんな解答になった。確実に修論のλ^V算法での証明地獄に毒されてる。でも 1^n が普通に任意の n について簡約で辿り着けてしまうので全然的外れてたっぽい。