パズルの国のアリス

コイン配置で勝負(問題)

坂井 公(筑波大学) 題字・イラスト:斉藤重之

 アリスは,ハンプティ・ダンプティとともに,久しぶりにトウィードルダムとトウィードルディーの双子兄弟をたずねてみた。すると,2人は,なぜかテーブルに1枚の紙を広げ,手元にたくさんのコインを積んで睨み合っていた。広げた紙の上にもコインが置かれている。そばには円をたくさん描いた紙が何枚かと足を開いたコンパスが2つ散らかっていた。

 いつも興味津津のアリスが「何してるんですか」ときいてみると,例によって双子が喧嘩していたら,仲裁に入った伯父さんが新しいゲームを教えてくれて,今はそれで勝負をしているところだという。

 「ルールは簡単なんだ。まず,先手が紙の上に好きな図形を描く。そのあとは,後手から始めて紙の上に半径1cmの円を交互に描いていくというだけのゲームだよ」とダム。

 「円の描き方にはもちろん制限がある」とディーが説明を引き継ぐ。「まず,円の中心はどこに置いてもよいが,最初に先手が描いた図形の中になければならない。円自体は,一部が図形の外にはみ出してもかまわないんだけどね。あと,円同士は互いに重なってはいけない」。 「そうして続けていくと,やがて重ならずには新しい円が描けなくなるだろ。その時の手番の者が負けだ」とダム。

 「それで試しに何回かやってみたんだけど,コンパスで円を描くのが面倒くさいなと思っていたら,このコインの半径がちょうど1cmだったことを思い出してね」とディーが自分の思いつきを自慢げに言う。

 「円を描く代わりにコインを載せていけばいいだろ。でも問題が少しあって,コインの中心が図形の中にあるかどうかの判定で意見が食い違うかもしれない。そこで,その判定を君たちにお願いできると助かるんだけど……」

 ということで,2人の喧嘩に巻き込まれてしまった感のあるアリスとハンプティだが,この辺で,読者には,簡単な問題でウォーミングアップをしてもらいたい。まず第1問としては,先手が最初に描く図形として長方形を選ぶと,先手には勝ち目がないということを証明していただこう。第2問としては,先手が自分の勝ちを確定するためには最初にどういう図形を描けばよいかを考えていただきたい。

 ゲームを実際に少しやってみるとわかると思うが,先手が描いた図形が小さく,少ない手数でコインが置けなくなるような場合は,勝負を読み切れることが多い。特に描く図形は単連結でなければならないという制限がある場合 (「単連結」という数学用語は,厳密に定義するのはいささか面倒だが,平面図形の場合,多角形や円のように,1つながりの閉曲線を境界に持つ図形と考えればよい),先手が勝つのは容易ではないようだ。調べてみると面白いだろう。

 双子は,先手が描く図形は単連結でなければならないとした上で,円が50個以上描かれる前に勝負がついた場合は引き分けとするという規定を入れてゲームをしていた。ハンプティは,散らばっている紙を拾い上げ眺めていたが,「ふーん。これは三角形の上で勝負したんだね。なるほど,ただの三角形とはいえ,これだけ大きいとなかなか勝負がつかないな。結局,100個目の円を描いた後,101個目がどうしても描けなくなってどちらかが負けたわけか」と言ったあと,突然,奇妙なことを言いだした。「おう,面白いことに気が付いたぞ。ということは,半径1cmの円が400個あれば,この三角形はそれらで完全に覆い尽くせるわけだ」。

 アリスも双子も,これをキョトンとして聞いていたが,読者には,最後の問題として,このハンプティの言葉の根拠を考えていただきたい。

解答はこちらです