角p5
目次へ戻る

上限: ((2n+1)(2m+1)+k)/12
ただし、k=3(n,mが奇数),1(n,mが奇数と偶数),-1(n,mが偶数と偶数)

…が整数となるとき、かつその時に限り、
上限の小数点以下切り捨てはMX値と一致しません

これらはすべて、「上限の切り捨て-1」がMX値となります。

たてよこをそれぞれn,m(n,mはともに1,2,3,5以外の自然数)としたとき、mod 6 で、
n,m
2,2
0,0
奇数,1
0,5
2,3



n,m 2,2

上限: ((2n+1)(2m+1)+k)/12 k=-1 の導出は、MX値2にある通り、
継ぎ目の数≧白マスの数-1
という不等式から出発しています。そして、n,mが2,2のとき、上限個の黒マスを入れると、ちょうど 継ぎ目の数=白マスの数-1 となります。継ぎ目の数の余裕がまったくありません。

継ぎ目の数=白マスの数-1 のとき、上限個の黒マスを入れるには、以下の条件を満たす必要があります。
・「2x2禁」…2マスx2マスの部分が全て白マスになってはならない。
2x2の白マスのかたまりは、白マス4個、継ぎ目も4個です。本来ならば白マス4個を継ぎ目3本でつなぐことができるのに、継ぎ目が多すぎます。このような部分があると、全体では継ぎ目の数=白マスの数-1を満たせません。
・「ループ禁」…白マスからなるループが形成されてはならない。
上と同様、継ぎ目を余分に消費してしまっています。
また、上限の導出の過程も考えると、以下も成り立ちます。
・盤面の角にあたる1マスが黒マスとなる
・盤面の辺にあたるマスに、最大限((n-2)/2+(m-2)/2個)黒マスが入る

では、上限個の黒マスが入らないことを背理法で示します。

例えば、たて14、よこ14のへやに上限個(70個)の黒マスを入れようとするとき、これらの条件を満たすために以下のように黒マス白マスが決まります。黒マスはへやの中に詰めるので、へやの外は白マスとなり、右下に2x2禁で黒マスが生じるところから、次々に決まります。

14x14


「ループ禁」より、全ての黒マスは"壁にアースされる"(その黒マスから斜めに黒マスを辿っていくと、壁に接する黒マスにたどり着くことができる)必要があります。さもなければ、その黒マスの周囲を白マスを辿ることで一周出来てしまいます。

よって、壁に接するマスが市松模様の片面にしかないので、もう一方の面のマスは全て黒マスが入りません(その黒マスをアースできない)。
したがって、下図のように白マスが決まります。
また、すでに黒マスと定まったマスや、残った空きマスを図のようにa,bと分類しておきます。

a,b分類


この先は、「奇数交点の補題」と同様の議論が進みます。aのマスのうち1つが白マスになったと仮定します。「2x2禁」より、その右上・右下・左上・左下のマス(いずれもbのマスです)は全て黒マスとなります。よって、白マスになったaのマスが分断しないよう、その上下左右のいずれか1つのaのマスが白マスになります。最終的には、aのマスのみを伝って、へやの外の白マスにたどり着く必要があります。
しかし、へやの左辺も下辺も、aのマスが全て黒マスとなっているため、へやの外にたどり着くことが出来ません。へやの左上の角のaのマスはすでに白マスですが、このマスから外に出ることは出来ません。よって矛盾し、上限はMX値ではありません。


黒マスを1つ減らせば、継ぎ目の数≧白マスの数-1 となり、左辺の方が3大きくなります。2x2やループを作っても良いことになります(一つ作ると、余分な3つの継ぎ目のうち1つ消費する)。また、盤面の角や辺に関する制約も緩くなります(辺の黒マスが一つ減っても、継ぎ目を1つ消費。また、角の黒マスは、2つ消費)
例えば、たて8、よこ14で、以下のように配置することが出来ます。

「下に6マス」

「右に6マス」

また、8x8でも入ります。右は、角のマスに入らない(2ペナ)例です。


よって、(上限-1)個がMX値になります。

n,m 0,0

このときも 継ぎ目の数=白マスの数-1 となります。
上と同様の議論で、このとき上限はMX値ではありません。
黒マスを1つ減らせば、継ぎ目の数≧白マスの数-1 となり、左辺の方が3大きくなります。
たて6、よこ6です。2x2が右上に2つ、左上にループが1つあり、継ぎ目3つ分の余裕を使っています。
「右に6マス」

「下に6マス」


よって、(上限-1)個がMX値になります。


n,m 1,(奇数)

このときも 継ぎ目の数=白マスの数-1 となります。つまり継ぎ目の余裕が無く、

・盤面の角にあたる1マスが黒マスとなる
・盤面の辺にあたるマスに、最大限((n-1)/2+(m-1)/2個)黒マスが入る
となってしまいます。

よって、「ループ禁」に反し、上限はMX値ではありません。

黒マスを1つ減らせば、継ぎ目の数≧白マスの数-1 となり、左辺の方が3大きくなります。
たて7、よこ7です。2x2が2つ出来ていて、辺が1減っているので、継ぎ目3つ分の余裕を使っています。

「下に2マス」

「右に6マス」


よって、(上限-1)個がMX値になります。


n,m 0,5

このときも 継ぎ目の数=白マスの数-1 となります。継ぎ目の余裕が無く、

・盤面の角にあたる1マスが黒マスとなる
・盤面の辺にあたるマスに、最大限((n-1)/2+(m-1)/2個)黒マスが入る
・「2x2禁」
を同時に満たすことが出来ません。下の図で、緑の部分に2x2が必ず生じます。

これは奇数x偶数で常に起こる現象です。

黒マスを1つ減らせば、継ぎ目の数≧白マスの数-1 となり、左辺の方が3大きくなります。
たて11、よこ12から、右6,下6と伸ばせます。



また、下の6x5から、右6を繰り返すこともできます(下6はおそらく出来ません。幅5ではこの議論が成り立たないためです。)。

よって、n≧6, m≧11では、(上限-1)個がMX値になります。

n,m 2,3
0,5と同様、黒マスを1つ減らす必要があり、このとき継ぎ目の数≧白マスの数-1 となり、左辺の方が3大きくなります。
たて8、よこ9から、右6,下6と伸ばせます。






目次へ戻る




このサイトは無料ホームページ作成.comで作成されています