パズルの国のアリス

アナゴ先生の美術作品(解答)

 まず最初の問題であるが,同色の4点が頂点をなす長方形を便宜上「同色長方形」と呼ぶことにしよう。2色に色分けされたキャンバス上には必ず同色長方形が存在するが,このことは英語で「pegionhole principle(PHP)」と呼ばれる原理を2重に使って証明するのが鮮やかだろう。PHPは,日本語では英語の直訳で「鳩の巣原理」と呼ばれることも多いが,「部屋割り論法」というほうが筆者の好みだ。ある人数の人をそれより少ない数の部屋に割り振ると,必ず相部屋ができてしまうという当たり前の事実を述べた法則である。

 まず,キャンバス上に3本の水平線を任意に引く。それらをh1h2h3としよう。次に垂直線v1を引くと,v1h1h2h3とそれぞれ1点で交わり,その交点の色を順にc11c12c13とすると,これらはそれぞれ黒か白のどちらかだから,可能性としては23=8通りがありうる。さらに,垂直線をv2,……,v9と増やして9本にすると,垂直線viそれぞれが3本の水平線と交わり,その交点の色をci1ci2ci3とすれば,この可能性は8通りしかなく,垂直線は9本あるから,この中には同じものがある。すなわち1≦ij≦9となるijci1cj1ci2cj2ci3cj3を満たすものがある。次にci1ci2ci3について考えると,これらは白か黒のどちらかだから,2つは同色だ。例えばci1ci2とすると,水平線h1h2と垂直線vivjの交点が同色長方形を形成する。

 以上の証明は色数が増えても通用することは明白だろう。例えば,色数がn色の場合,キャンバスに引く水平線をn+1本,垂直線をnn+1+1本にするだけで,証明の細部を変えずにほとんどそのままで機能する。

 こうして,アナゴ先生の望みは色数が何色あろうと達成されないことが証明されてしまったが,その望みが「ちょうど10cm離れた同色の2点が存在しないような作品を作りたい」というものだったらどうか? これも不可能な望みだが,実は,不可能性の証明はずっと簡単だ。キャンバスは1m×1mだから,その上に1辺が10cmの正三角形を描くのは易しい。その正三角形の3つの頂点の色を考えよう。それは白か黒だから少なくとも2つは同じ色だ。よって,その2頂点が10cm 離れた同色の2点を形成し,望みは決して達成されないことがわかる。

 では,色数が増えてもこの望みは不可能だろうか? 不可能な場合でも,それを証明するのは,易しくない。例えば3色の場合,互いに10cm離れた4つの点をキャンバス上に見つけることができれば,PHPによりそのうち2つは同色になるのだが,そのような4点は3次元以上の空間でなければ存在しない。3色で2次元の場合に不可能であることを証明するには,例えば次のようにするのがよいだろう。

 10cm離れた同色の2点が存在しないと仮定しよう。1辺10cmの正三角形を2つ貼り合わせた下図左のような菱形ならキャンバス上に描くことができる。仮定より,点A,B,Cはすべて異なる色だ。また,点A,B,Dもそうだ。色は3色しかないのだから,CとDは同色でなければならない。CとDの距離は簡単な計算で10√3cmとわかるので,一般に10√3cm離れた2点は,下図左のような菱形をキャンバス上に描ける場合,同色でなければならない。そこで,次は下図右のような二等辺三角形を考えてみる。EFとEGは10√3cmでFGは10cmである。先の考察から,EとF,EとGはそれぞれ同色だ。したがってFとGも同色だが,これは10cm離れた同色の2点が存在しないという仮定に矛盾する。

 こうして色数が3色の場合には,上図右のような図形が描けるほどにキャンバスが大きければ,10cm離れた同色の2点が必ず存在することが証明できる。では,十分大きいキャンバスであれば,色数がどんなに多くても,10cm離れた同色の2点が必ず存在するのだろうか? 実はそうではない。

 ちょっと意外に思われる読者も多かろうが,実際,色数が7色あると,どんなに大きいキャンバスであっても10cm離れたどの2点も異なる色を持つように色分けすることができる。下図のハチの巣のような模様をご覧いただきたい。各六角形の部屋の中の数値はそこを特定の色に塗ることを表している。例えば,数値0の六角形の部屋はすべて白,1の部屋はすべて赤で塗るといった具合だ。六角形の頂点や辺上の点は,それが境界となっている領域のどれかと同じ色に塗る。

 各六角形の1辺の長さをacmとすると,1つの六角形領域の内部あるいはその外周上の点どうしは離れていてもせいぜい2acmである。また,同じ色に塗る異なる領域の点は,簡単な計算で最低でも√7acm以上離れていることがわかる。従って,2a<10<√7aとなるようにaを決めて(例えばa=4.5),上図のようにキャンバス全体を塗り分けてやれば,互いに10cm離れた点の対で同じ色を持つものは生じえないことがわかる。

 色数が5色や6色の場合,7色の場合と同様にキャンバスを色分けできるか,あるいは10cm離れた同色の2点が必ずできてしまうかは筆者の知る限り未解決だ。4色の場合に10cm離れた同色の2点が必ずできてしまうことが,コンピューターの助けを借りて2018年に証明されたらしいが,これを紹介するのは筆者の手に余る。読者の研究を期待したい。興味を持たれた読者は「chromatic number」や「彩色数」という言葉でウェブ検索されるとよいだろう。

問題はこちらです