1998年東大後期数学第3問

グラフ理論ではないしグラフですらない。列。

解法

両端にダミーの頂点を追加すると、操作 1$1$ は操作 2$2$ で表現できる。 よって操作 2$2$ だけを考えればよい。 最初の頂点も操作 2$2$ で作ることにすれば、問題は以下のように言い換えられる。

頂点 2$2$ つが辺で結ばれている。 操作 2$2$ を好きな回数繰り返して両端以外の全ての頂点を白くするとき、パスの長さ (辺の本数) として取り得る値は何か。

mod3$mod3$ で 1$1$ と 2$2$ の長さ全てが作れることは簡単に分かる (辺の本数で長さを定義したので 1$1$ ずれているが本質ではない)。 必要性を示す。

定理

2$2$ つの頂点が辺で結ばれており、何らかの色が付いている。 操作 2$2$ を好きな回数繰り返して両端以外の全ての頂点が白くなったとき、以下のいずれかに該当する。

(i)$(\mathrm{i})$ 長さが 1(mod3)$1(\mathrm{mod}3)$ で、両端はいずれも偶数回色が変化した

(ii)$(\mathrm{i}\mathrm{i})$ 長さが 2(mod3)$2(\mathrm{mod}3)$ で、両端はいずれも奇数回色が変化した

証明

パスの長さについての帰納法を用いる。 パスの長さが 1$1$ の場合は自明である。

パスの長さが 2$2$ 以上の場合、少なくとも 1$1$ 回は操作をしている。 最初の操作によって追加された頂点を c$c$ とする。 以降の操作は c$c$ より左に行われるものと c$c$ より右に行われるものに分けられる。 最終的に両端以外が白になっていることから、c$c$ の左右でそれぞれ帰納法の仮定が適用できる。

最終状態において c$c$ より左の部分 (c$c$ を含む) を L$L$、c$c$ より右の部分 (c$c$ を含む) を R$R$ とする。 L,R$L,R$ のそれぞれに帰納法の仮定を適用すると、c$c$ が白になっていることから、両者とも (i)$(\mathrm{i})$ に該当するか、両者とも (ii)$(\mathrm{i}\mathrm{i})$ に該当するかのいずれかである。

• 両者 (i)$(\mathrm{i})$ の場合、全体の長さは 2(mod3)$2(\mathrm{mod}3)$ であり、両端は最初の操作で 1$1$ 回変化したことを踏まえると奇数回色が変化している。これは (ii)$(\mathrm{i}\mathrm{i})$ に該当する。
• 両者 (ii)$(\mathrm{i}\mathrm{i})$ の場合、全体の長さは 1(mod3)$1(\mathrm{mod}3)$ であり、両端は最初の操作で 1$1$ 回変化したことを踏まえると偶数回色が変化している。これは (i)$(\mathrm{i})$ に該当する。

よっていずれも定理の主張に該当する。 ■$◼$

余談

操作を最初の 1$1$ 回とそれ以降とに分けるのはポリアの壺にも有効な考え方である。 尤も、ポリアの壺には一旦全ての球を区別するという簡潔な解法が存在するが。