第292回　グラフ理論：僕らは隣接探偵団（後編）

$ \newcommand{\HIRANO}{\unicode[sans-serif,STIXGeneral]{x306E}} \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} $

僕の部屋

僕「ユーリが推理した必勝法はこういうことだね。でも、推理は推理に過ぎない。証明しないと」

ユーリ「お兄ちゃんが言った通り、小さい数で試したよ！　まず、頂点が$1$個だと、後手必勝！」

僕「頂点が$2$個の場合は、先手必勝だね」

ユーリ「ははーん……」

僕「何か気がついた？」

ユーリ「頂点が$1$個の場合、頂点が$2$個の場合と来たら……」

僕「と来たら……」

ユーリ「お兄ちゃんの大好きな一般化だ！　頂点が$n$個の場合を考えるんでしょ？　でしょでしょ？」

僕「ええっ？」

ユーリ「へ？　違うの？」

僕「いや、それは《早すぎる一般化》だと思うよ。$1$個、$2$個と来たら、頂点が$3$個の場合も考えようよ」

ユーリ「えー、めんどいよー」

頂点が$3$個の場合

僕「頂点が$3$個の場合、どんなふうに《連結ゲーム》が進むか考えてみよう」

ユーリ「あー、先手は$3$通りあるじゃん？」

僕「うん、確かに$3$通り描けるけれど、つながり方を考えると、実質的には$1$通りしかないと考えてもいいよね」

ユーリ「あ、そーだね。どこかの$2$点がつながるだけだから」

僕「これに対して、後手の描き方は？」

ユーリ「後手は……うん、これは$2$通りあるけど、ジッシツテキには$1$通り？　裏返して考えたら」

僕「うん、$1$通りだね。裏返してもいいし、鏡に映してもいい」

ユーリ「これでもう先手は描けないから勝負あった！　頂点が$3$個のときは後手必勝だ！」

僕「うん、そうだね」

ユーリ「さてさて、お待ちかねの一般化！」

僕「いやいや、まだ具体例を考えていこうよ」

ユーリ「どしたのお兄ちゃん。いつもならそろそろ《文字の導入による一般化》じゃあ！　って腕まくりするとこじゃん？　キャラ壊れたの？」

僕「だって、まだこれじゃ一般化できそうにないからね」

ユーリ「えー、そっかなー。だっていつもなら《頂点が$n$個の場合》から《頂点が$n + 1$個の場合》へと華麗に進むでしょー？」

僕「ユーリがいってるのは、《数学的帰納法》を使うって意味だよね」

ユーリ「それそれ、そーゆーやつ。ステップＡはめっちゃ簡単で、ステップＢが華麗なやつ」

ユーリ「奇数と偶数、交互に進むから、簡単に証明できんじゃないの？」

頂点が$4$個の場合

僕「……うん、大まかにはわかってきたけど、やっぱり《頂点が$4$個の場合》を考えよう」

ユーリ「へいへい、お兄ちゃんには逆らえませんな。$4$個並べますとも」

僕「まず先手は……」

ユーリ「先手は、えーと……何通り？」

僕「つながり方を考えれば、この$1$通りだよ」

ユーリ「あー、そっか。そーだね……」

僕「単純化して進まないと、考える場合の数が増えちゃうから気を付けないと」

ユーリ「次は後手でしょ。後手も$1$通り……んにゃ！　$2$通りある！　辺をつなげるのと、辺をバラけさせるのと」

僕「次は先手に戻るんだけど、二つの場合のそれぞれを考えなくちゃいけなくなる……」

ユーリ「うわあ……すでにめんどくさい……」

僕「……あれ？」

ユーリ「②と③のジグザグは結局同じだよね？」

僕「そうだね。つまり、頂点$4$個から始めて、先手→後手→先手と来たときにできるグラフは、この$2$通りになる。そしてこれ以上は辺は引けない」

ユーリ「そっかー、場合の数がぞくぞく増えるようだけど、実際は同じになったりするんだね！　んじゃ、そろそろ一般化に参りますか」

僕「そうだね。じゃあ、証明するよ。まず……」

ユーリ「まって。ユーリ、謎を解いちゃったもん！」

僕「え？」

ユーリ「あのね、ユーリは名探偵なのじゃ。すでに謎はすべて解けておるのじゃ。まずは聞きたまえ」

僕「聞いてるよ」