有名な東大の問題

1998年の東大の後期入試の問題で、「大学入試史上で最も難しい問題」といわれているみたいですがグラフ理論の問題なので、解いてみることにします。

問題文にある二つの操作(白頂点の追加、辺の細分）をそれぞれ(I), (II)と記すことにします。

小さい例で試すと、
長さ$3n+2$のパスは生成できなくて、長さ$3n$もしくは$3n+1$のパスは生成できないっぽいので答えとしてはこれになることが簡単に予想できると思います。でも長さ$3n+2$のパスが生成できないことを示すのが難しいです。

少し考えて見ると, 長さ$3n+2$の白パスは、黒丸からスタートすれば生成できる、ということが分かります。
ここでいう「パス」とは一本になっているグラフのことで、色は何でも良いこととします。（細かいことですが、頂点にラベルは付いておらず、左右反転して得られるものは異なるパスであると約束します）

そこで、補題として

「黒丸から生成できるパス」の全体と「白丸から生成できるパス」の全体がdisjointであることを示せばよいことになります。（これが言えれば、黒丸から生成できるパスは白丸から生成できないことになるので証明が完了する)

この補題を示すために、パスに対して不変量を考えることにします。つまりパス$P$に対して, $f(P)$という値を考え、白丸から得られるパスの不変量$f(P_1)$と黒丸から得られるパスの不変量$f(P_2)$が、どんな$P_1,P_2$に対しても必ず$f(P_1)\neq f(P_2)$になるということが示すことが出来れば、白丸から得られてしかも同時に黒丸からも得られるようなパス$P$が存在しない、つまり補題が成り立つことが示せることになります。

細かい証明とかは省きますが、不変量として
$f(P)=(2^{m-1}\cdot x_1 + 2^{m-2}\cdot x_2 + \cdots + 2^0\cdot x_m + n)$ mod $3$.
というのを考えます。
ここで$n$はパス$P$の頂点数、$m$はパス$P$が含む黒頂点の個数、$x_i$はパスを横に並べて書いたときに右から$i$番目にある黒頂点の座標(1-indexで考えていて、例えば1番右なら1, 右から2番目なら2, $\ldots$)です。

ローリングハッシュみたいな形の式をしていますが、この不変量を考えると
$P$が白丸から生成されるときは必ず $f(P)\in \{0,1\}$
$P$が黒丸から生成されるときは必ず $f(P) = 2$
となること分かり、証明が完了します。

不変量となっていることの証明は、操作(I), (II)それぞれの逆操作を考えて帰納法を使えばいけます。