- 21 名前：１３２人目の素数さん mailto:sage [2011/06/23(木) 17:40:27.77 ]
- 四色問題を変形した問題。どちらも自分には解けてません(＾o＾)
問題1：重なりを持たない長方形I1, I2, …, Ik
(辺や頂点が共有されるのは良いとする)を
何色かの色で塗り分ける。次のような制限を課す。
「 Ii∩Ij≠φ のとき、IiとIjは違う色で塗らなければならない 」
この制限のもと、4色あれば必ず塗り分け可能であることを示せ。
例：「田」の字になっている4つの正方形は、3色では塗り分けできず、
ちょうど4色で塗り分けられる。
問題2：上の問題を自然にn次元に一般化する。
R^nの "超直方体" I1, I2, …, Ik は重なりを持たないとし、
同じ制限のもとで塗り分ける。このとき、2^n 色あれば
必ず塗り分け可能であることを示せ。
例：「田」の字をn次元に一般化したような立体を考えると、
この立体は2^n個の超立方体で構成される。これらは2^n−1色では
塗り分けできず、ちょうど2^n色で塗り分けできる。
