1998年(平成10年)東京大学後期-数学[3] - [別館]球面倶楽部零八式markIISR

2024.02.07記

[3] グラフ $G=(V,W)$ とは有限個の頂点の集合 $V=\{\mbox{P}_1,…,\mbox{P}_n\}$ とそれらの間を結ぶ辺の集合 $W=\{E_1,…,E_m\}$ からなる図形をする．各辺 $E_j$ は丁度2つの頂点 $\mbox{P}_{i_1}$ ， $\mbox{P}_{i_2}$ $(i_1 \neq i_2)$ を持つ．頂点以外での辺同士の交わりは考えない．さらに，各頂点には白か黒の色がついていると仮定する．

例えば，図1のグラフは頂点が $n=5$ 個，辺が $m=4$ 個あり，辺 $E_i$ （ $i=1$ ，…， $4$ ）の頂点は $\mbox{P}_i$ と $\mbox{P}_5$ である． $\mbox{P}_1$ ， $\mbox{P}_2$ は白頂点であり， $\mbox{P}_3$ ， $\mbox{P}_4$ ， $\mbox{P}_5$ は黒頂点である．

出発点とするグラフ $G_1$ （図2）は， $n=1$ ， $m=0$ であり，ただ1つの頂点は白頂点であるとする．

与えられたグラフ $G=(V,W)$ から新しいグラフ $G'=(V',W')$ を作る． $2$ 種類の操作を以下で定義する．これらの操作では頂点と辺の数がそれぞれ1だけ増加する．

（操作1）この操作は $G$ の頂点 $\mbox{P}_{i_0}$ を $1$ つ選ぶと定まる． $V'$ は $V$ に新しい頂点 $\mbox{P}_{n+1}$ を加えたものとする． $W'$ は $W$ に新しい辺 $E_{m+1}$ を加えたものとする．
$E_{m+1}$ の頂点は $\mbox{P}_{i_0}$ と $\mbox{P}_{n+1}$ とし， $G'$ のそれ以外の辺の頂点は $G$ での対応する辺の頂点と同じとする． $G$ において頂点 $\mbox{P}_{i_0}$ の色が白又は黒ならば， $G'$ における色はそれぞれ黒又は白に変化させる．それ以外の頂点の色は変化させない．また $\mbox{P}_{n+1}$ は白頂点にする（図3）．

（操作2）この操作は $G$ の辺 $E_{j_0}$ を1つ選ぶと定まる．
$V'$ は $V$ に新しい頂点 $\mbox{P}_{n+1}$ を加えたものとする． $W'$ は $W$ から $E_{j_0}$ を取り去り，新しい辺 $E_{m+1}$ ， $E_{m+2}$ を加えたものとする． $E_{j_0}$ の頂点が $\mbox{P}_{i_1}$ と $\mbox{P}_{i_2}$ であるとき， $E_{m+1}$ の頂点は $\mbox{P}_{i_1}$ と $\mbox{P}_{n+1}$ であり，
$E_{m+2}$ の頂点は $\mbox{P}_{i_2}$ と $\mbox{P}_{n+1}$ であるとする．
$G'$ のそれ以外の辺の頂点は $G$ での対応する辺の頂点と同じとする． $G$ において頂点 $\mbox{P}_{i_1}$ の色が白又は黒ならば， $G'$ における色はそれぞれ黒又は白に変化させる． $\mbox{P}_{i_2}$ についても同様に変化させる．それ以外の頂点の色は変化させない．また $\mbox{P}_{n+1}$ は白頂点にする（図4）．

出発点のグラフ $G_1$ にこれら $2$ 種類の操作を有限回繰り返し施して得られるグラフを可能グラフと呼ぶことにする．次の問いに答えよ．

(1) 図5の $3$ つのグラフはすべて可能グラフであることを示せ．ここで，すべての頂点の色は白である．

(2) $n$ を自然数とするとき， $n$ 個の頂点を持つ図6のような棒状グラフが可能グラフになるために $n$ の満たすべき必要十分条件を求めよ．ここで，すべての頂点の色は白である．

2019.04.03記

大学入試史上最難問と名高いこの問題の元ネタは、首都大学東京の小林正典先生の研究
https://www.mathsoc.jp/publication/tushin/2202/2202kobayashi.pdf
です。この pdf は日本数学会2017年度年会における市民講演会(2017年3月26日)の資料です。私も聞きに行きました。当時の予備校の速報の話については2003年に刊行された

入試数学　伝説の良問100　良い問題で良い解法を学ぶ (ブルーバックス)

作者:安田亨
講談社

Amazon

に書いてあり、ここに黒白を行列の置きかえて不変量を計算する解法が述べられています。この行列への置き換えというトリッキーな解法は web page のあちこちで紹介されていますが、私の知る限り、安田亨さんの本が一番古い。なお本家小林先生の上記の pdf に別解がありますが、行列の余因子展開から導かれた漸化式によって不変量を求めています(その過程をまだ確認していない)。

2020.03.26追記