第292回 シーズン30 エピソード2

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

僕の部屋

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

ユーリ「お兄ちゃんが言った通り、小さい数で試したよ！　まず、頂点が $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$ 通りになる。そしてこれ以上は辺は引けない」

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

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

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

僕「え？」

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

僕「聞いてるよ」