角Page 3



1xnのとき

nが偶数→MX=n/2 解はn/2+1個
nが奇数→MX=(n-1)/2 唯一解

2xnのとき

n=4k+p(kは整数、p=0,1,2,3)となるようk,pを定める。
図はn=19(k=4,p=3)を切り分けたものである。


端の4x2のMX値が3であり、実際に上のような詰め方が存在することより、
MX値は、nが4増えるごとに3増えていく。

p=0
MX=n*3/4+0
p=1
MX=(n-1)*3/4+1
p=2
MX=(n-2)*3/4+2
p=3
MX=(n-3)*3/4+2

p=2のみ、kによらず唯一解である。


3xnのとき

n=8k+p(kは整数、p=0,1,2,3,4,5,6,7)となるようk,pを定める。
図はn=20(k=2,p=4)である。

端の8x3のMX値が9であり、実際に上のような詰め方が存在することより、
MX値は、nが8増えるごとに9増えていく。

p=0
MX=n*9/8
p=1
MX=(n-1)*9/8+2
p=2
MX=(n-2)*9/8+2
p=3
MX=(n-3)*9/8+4
p=4
MX=(n-4)*9/8+5
p=5
MX=(n-5)*9/8+6
p=6
MX=(n-6)*9/8+7
p=7
MX=(n-7)*9/8+8

p=1のとき唯一解である。
p=3のとき、k=0(n=3)で唯一解である。
k≧1では以下のような別解がある。




5xnのとき


n=16k+p(kは整数、0≦p≦15)となるようk,pを定める。
p=0,1,2,3,4,05,06,07,08,09,10,11,12,13,14,15のとき、
b=0,3,4,6,8,10,11,13,15,17,19,21,22,24,26,28とし、
MX=(n-p)*29/16+b

DPによる探索の結果、上の式がk≦5(n≦95)までで成り立っている。

p=1,10のとき、0≦k≦8で唯一解である。
p=5のとき、k=0で唯一解である。
k≧1では以下のような別解がある。



端の15x5がMX値29で、このとき唯一解。(16x5はMX値30で複数解)



以下、nが十分大きい場合を考える。

5xnのとき、端に黒マス5連続(下図)だと、ここからどう埋めても余裕値を消費してしまう。
(=ここからどう黒マスを埋めても、白マスの「2x2禁」「ループ禁」を破ってしまう)


4連続なら、余裕値を消費しない(=「2x2禁」「ループ禁」を破らずに済む)入れ方があり、
それは以下の通り。

しかも上の入れ方しか存在しない。下図は余裕値を消費する。

また、黒マス4連+4連でも、ここから黒マスをどう入れても余裕値を消費する。

もちろん「盤面の端に黒マスを最大限入れる」必要もあり、盤面の端の黒マスが1つ減ると余裕値を1消費する。

これらの消費を最小限に抑えるには、
「端に最大限黒マスを入れる:4,3,4,3,...を繰り返す。」
「「2x2禁」「ループ禁」を一度も破らない」
を満たす、以下のような詰め方が最密になる。


よって十分大きなnでも、この29個・16マス周期よりも余裕値を消費しない詰め方は存在しない。






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