第292回 グラフ理論:僕らは隣接探偵団(後編)

新シーズン「グラフ理論」開始! ユーリと「僕」が楽しむ《連結ゲーム》の必勝法を探っているうちに……

登場人物紹介

:数学が好きな高校生。

ユーリのいとこの中学生。 のことを《お兄ちゃん》と呼ぶ。 論理的な話は好きだが飽きっぽい。

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

僕の部屋

高校生のと中学生のユーリ《連結ゲーム》を楽しんでいた(第291回参照)。

の必勝法を見抜いたユーリは、 ほんとうにそれが必勝法になっているかを証明しようとしている。

《連結ゲーム》のルール

プレイヤーは二人。 紙に$1$個以上の頂点を描き、交互に二頂点を結ぶを描く。 先に描けなくなったプレイヤーが負けである。

辺を描くときのルールが三つある。

ルール1:辺は多重にしない

ルール2:ループを作らない

ルール3:サイクルを作らない

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

ユーリの推理

《連結ゲーム》では、最初に描いた頂点の数で勝者が決まる。

  • 奇数個ならば、後手必勝になる。
  • 偶数個ならば、先手必勝になる。

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

頂点が$1$個の場合

頂点が$1$個の場合、もう辺は描けない。 無理に描こうとするとループになってしまうので《ルール2》に反する。 だから、先手になった方が負ける。

$1$は奇数だから、確かに「奇数個ならば、後手必勝」になっている。

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

頂点が$2$個の場合

頂点が$2$個の場合、先手が結ぶ辺は一種類しかない。

後手がさらに無理に描こうとすると辺が多重になるか、ループになってしまう。

辺が多重になったら《ルール1》に反する。

ループになったら《ルール2》に反する。

だから、後手になった方が必ず負ける。

$2$は偶数だから、確かに「偶数個ならば、先手必勝」になっている。

ユーリ「ははーん……」

「何か気がついた?」

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

「と来たら……」

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

「ええっ?」

ユーリ「へ? 違うの?」

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

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

頂点が$3$個の場合

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

頂点が$3$個の場合

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

頂点が$3$個の場合、先手ははじめに$3$通りの辺を描くことができる

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

頂点が$3$個の場合、先手が描ける辺は実質的に$1$通り

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

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

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

頂点が$3$個の場合、後手が描ける辺は$2$通りあるけれど……

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

頂点が$3$個の場合、後手が描ける辺は実質的に$1$通り

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

「うん、そうだね」

頂点が$3$個の場合

頂点が$3$個の場合、先手が描ける辺は実質的に一種類しかない。

それに対して後手が描ける辺も実質的に一種類しかない。

それに対して先手が描ける辺はない。

だから、先手になった方が必ず負ける。

$3$は奇数だから、確かに「奇数個ならば、後手必勝」になっている。

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

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

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

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

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

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

数学的帰納法

どんな正の整数$n$についても条件$P(n)$が成り立つことを証明するには、次の二つのステップを踏めばいい。

ステップA:$P(1)$が成り立つことを証明する。

ステップB:任意の正の整数$n$について「$P(n)$が成り立つならば、$P(n + 1)$も成り立つ」ことを証明する。

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

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

ユーリの推理

《連結ゲーム》では、最初に描いた頂点の数で勝者が決まる。

  • 奇数個ならば、後手必勝になる。
  • 偶数個ならば、先手必勝になる。

これを証明したい!

頂点が$4$個の場合

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

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

頂点が$4$個の場合

「まず先手は……」

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

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

頂点が$4$個の場合、先手の描き方

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

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

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

頂点が$4$個の場合、後手の描き方

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

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

僕たちは、議論しながら先手のパターンを調べて、①②③を得た。

頂点が$4$個の場合、先手の描き方

「……あれ?」

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

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

頂点が$4$個の場合、勝負が付くパターンは$2$通りある

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

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

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

「え?」

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

「聞いてるよ」

この続きは有料会員登録をすると
読むことができます。
cakes会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の中高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わいましょう。本シリーズはすでに13巻以上も書籍化されている大人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

chibio6 数学的帰納法での証明、私も間違えたけど最後に頂点が1個増えるというだけではゲームの… https://t.co/wWOTylKXsu 4ヶ月前 replyretweetfavorite

aramisakihime 用語の定義は必要ですが、ゲームのルールがひとつだけで表せるとうれしくなりますね。 4ヶ月前 replyretweetfavorite

ogtkzk 頂点と連結、頭いいなぁ https://t.co/zfeaH3i4hM 4ヶ月前 replyretweetfavorite

cogitoergosumkm https://t.co/rwTlmWWMw1 数学ガール朝読めなかったので今読んだ まあ連結ゲームは名前からしてネタバレでしたね ところで、ルール0⇔ルール1,2,3を示すべきところルール0⇒ルール1,2,3しか示されていないように見えた 4ヶ月前 replyretweetfavorite