クイズ大陸クイズ大陸

参加型クイズサイト『クイズ大陸』へようこそ!
(2016/09/12) クイズの問題文中に画像を添付できるようになりました。
(2016/04/25) 投稿キーの受付を再開しました。

FAQ
feedRSS


n色問題(n<4)
難易度:★★★★  
?yard 2018/05/12 01:34
境界線によって囲まれた平面上の複数の領域を、隣り合う領域の色が全て異なるように塗り分けるとき、必要色は多くても4色であることが知られています。 2色、3色で塗り分けられる場合も当然あります。

(1)始点と終点が同じ一筆書きの線によって囲まれた平面上の複数の領域を同じ条件で塗り分けるとき、
 2色あれば十分であることを説明してください。

(2)一筆書きの線によって囲まれた平面上の複数の領域を同じ条件で塗り分けるとき、
 3色あれば十分であることを説明してください。

(3)鋭角三角形のみからなる平面上の複数の領域を同じ条件で塗り分けるとき、
 3色あれば十分であることを説明してください。

(4)三角形のみからなる平面上の複数の領域を同じ条件で塗り分けるとき、
 4色必要な場合があることを説明してください。


出題者でありながら、説明のうまい表現をまだ見つけ切れていません。
分かりやすい説明を思いついたら、ぜひ教えてください。
Answer(1)
ある領域を色Aで塗る。その後、最初に色を塗った領域から
 ・間に偶数個(0個を含む)のマスを介して行ける領域をB色
 ・間に奇数個のマスを介して行ける領域をA色 でそれぞれ塗る。
条件より、書いた線によってできる頂点は全て偶点(偶数本の線が伸びる頂点)であるから、
A色とB色の両方の条件を満たすようなマスは存在しえない。
よって、全ての領域は、最初に塗った領域を基準として2色で塗れる。


(2)
一筆書きの線の始点と終点を、元の問題の偶点を通らないよう繋ぐ(この線を、線Xと呼ぶ)。
元の問題の線と線Xによって分けられた領域は、(1)より2色A,Bで塗ることが出来る。 ...(a)
ここで、元の問題の線によって分けられていた領域のうち、「線Xが通る領域」と、それに
隣接する領域を考える。
線Xが通る領域の色を、順にA,B,A,B,…と確定させていく。すると、線Xの左と右で交互に
同じ色が接する部分が現れるので、同じ色の2領域のうち線Xが通っていないほうを色Cで塗る。
残りの領域は、(a)の時と同じ色で塗りつぶしていくことで、全ての領域は3色で塗られる。


(3)
補題:全ての頂点には、4つ以上の領域が接している。
補題証明:
鋭角三角形の全ての角は90度未満である。
(a)ある三角形の辺上にある頂点の場合
 鋭角のみを合わせて180度を作る場合、最低3個は角が必要である。
 対象の頂点を辺上に持つ三角形を含めて、この頂点には4個以上の領域が接している。
(b)どの三角形の辺上にも無い頂点の場合
 鋭角のみを合わせて360度を作る場合、最低5個は角が必要である。
 よって、この頂点には5個以上の領域が接している。

ある領域を色Aで塗る。この領域と辺で接するすべての領域を色Bで塗る。
補題より、この時点で色Bの領域どうしで接する部分は無い。
以降、色のついた領域と色のついていない領域の両方が接している頂点について、
色のついていない領域の接している数が少ない頂点から順に、「その頂点に接している
色のついていない全ての領域に、条件を満たすように色を塗る」作業を繰り返す。
周りの領域すべてがこのルールによって他の頂点により着色されるような頂点は補題より
存在しえないので、この方法により全ての領域は3色で塗られる。

(4)3色で塗れない例。
 https://gyazo.com/77a1e119c13ab278b6d6884e25d6570e
■
回答募集は終了しました。

このクイズのヒント

    ヒント知らないよ

このクイズの参加者(1人)

ジャンル・キーワード

携帯用ページ


携帯電話のQRコード読み取り機能でこのページを見られます。

広告 お買い物は下記のリンクからどうぞ

広告
クイズ大陸関連書籍