超へやわけMXのノート
MX値の上界に関する議論、余裕値について
超へやわけMX(リンク切れ)(2019/3/31 Yahoo!ジオシティーズのサービス終了により公開終了)では、空中のへやにおけるMX値の一般解が求められ(2003/1/27～2008/12/8)、証明も示されています。 すなわち、MXは以下の通り。ただしfloor(X)でXの小数点以下切り捨ての値を表す。
1xnのへや
MX=floor((n+1)/2)
3xnのへや
nが4の倍数なら
MX=5n/4
それ以外の時
MX=floor(5(n+1)/4)
nxnで、非負整数kでn=2^k-1と書けるときのへや(n=1,3を含む)
MX=((n+1)(n+1)-1)/3
以上のいずれも満たさない場合で、nxmのへや
nもmも奇数なら
MX=floor(((n+1)(m+1)-2)/3)
それ以外のとき
MX=floor(((n+1)(m+1)-3)/3)
唯一解となるのは以下のへや（「打ち上げ花火系列」と幅1,3）に限る。ただしkは任意の正の整数。
((4^k-1)/3)in(2^k-1)x(2^k-1)
(k-1)in(2k-1)x1
(5k)in(4k-1)x3
以下の文章は、証明の鍵となる「余裕値」の登場までの説明です。超へやわけMXの原文を転載したものではなく、私の独自の表現も交えています。アイデアや定理は、サイトの著者であるAsaokitan氏をはじめとした多数の方々の協同により生まれたものであり、この文章はそれを読んだ私のノートに過ぎません。
ペンシルパズル・へやわけにおいて、満たすべきルールは以下の4つである:
1.数字の数だけ黒マスを入れる。
2.隣接禁; 黒マスどうしが隣り合わない。
3.分断禁; 黒マスによって盤面が分断されない。
4.三連禁; たてよこに3へやにわたって、白マスが連続しない。
2. 隣接禁と3. 分断禁のルールを満たしたまま、黒マスを出来るだけ多く入れ、数字を出来るだけ大きくすることを考える。その最大値をMX値と呼ぶ。
2.隣接禁のみを考えるならば、へやを市松模様に塗り分け、一方を全て黒マスにすれば、最も多くの黒マスが入る。この入れ方は多くは3. 分断禁に反する。
黒マスや盤面の壁に囲まれて孤立した白マス群をシマと呼ぶ。外を大きく囲む白マス群から（これはシマには数えない）、孤立してしまっている白マスのかたまり、シマが生じる。
3. 分断禁は、「盤面にシマが現れてはいけない」と言い換えられる。
市松模様の入れ方から黒マスを取り除いて、シマの個数を0まで減らすことを考える。黒マスを出来るだけ多く入れることを考えると、黒マスの最低限の除去で、シマを効率良く減らす必要がある。
定理1-1 しまつぶし原理
ある黒マスを白マスに変えることで減らせるシマの数は、最大3。
証明: その黒マスに隣接するマスは最大4マス。その4マスが別々のシマに属する時、シマが最も多く減る。このとき、黒マスを白マスにすると大きな1つのシマに合体するから、シマの数は3つ減る。（隣接する4マスのうち、1マスが外を大きく囲む白マス群の一部であったとしても、同様にシマの数は最大3つ減る。）
ここで、へやを市松模様に塗り分け、一方を「A面」、もう一方を「B面」と呼ぶことにする。ただし、へやの面積が奇数であるとき、マス数の多いほうをA面とする。A面に全て黒マスを入れたときに生じるシマを「元ジマ」と呼ぶことにする。
定理1-2 しまつぶし公式
黒マスの入れ方ごとに、余裕値Rを、R=3(A-K)-Sと定義する。
ただし、AはA面のマス数、Sは元ジマの数、Kは入れている黒マスの数。
黒マスがルールを満たしている状態で入っているとき、R>=0。
証明: A面に全て黒マスを入れた状態から、今の入れ方になるまで、除去した黒マスの数は(A-K)個。定理1-1より、減らした元ジマの数は最大でも3(A-K)個。黒マスがルールを満たしている状態で入っているので、これはSより大きい。
この定理の対偶より、Kが大きすぎてR<0になってしまうと、K個の黒マスがどのように入れられていても、それがルールを満たしていない入れ方であることが示される。MX値を上から押さえる重要な式である。
シマを(3-x)個しか減らさずに黒マスを1つ除去することを、「余裕値Rをxだけ消費する」と呼ぶ。A面に全て黒マスを入れた状態から実際に黒マスを減らしていくとき、余裕値の消費量がRを超えないようにする必要がある。これをしまつぶし規則と呼ぶ。
以降、証明は以下のように続きます。
B面に黒マスが入るとき（A面の黒マスを上手く除いて、B面に黒マスを入れられるような隙間が生じる場合）を考える。そして、このときトータルではシマの減少数が黒マスの減少数の3倍に満たず、余裕値が1以上消費されてしまうことを示す(定理1-3 ビショップの定理)。
1xn, 3xnのMX値を個別に証明する。
定理1-2からMX値の上界をへやのサイズの式で表す(定理2-1 とくしんの定理)。
nxmのへやでnとmが奇数のときMX≦floor((n+1)(m+1)-1)/3)となるが、等号成立条件が厳しいことを示す（補題2-2 奇数交点の補題 奇数×奇数のへやでR=0のとき、座標が(奇数、奇数)のマスをPとすると、Pは黒。）
証明: 余裕値を消費できないので、B面はすべて白で、外周の(1,奇数)の黒マスは除けない。仮にPが白と仮定すると、Pと斜めに隣り合う黒マスは除けない。よってPとタテヨコに2マス離れた別の(奇数、奇数)のうち一つ以上が白。これを繰り返すと、Pのシマが外側に脱出するには外周の黒マスを除く必要が出てきてしまう。よって矛盾。
これは定理2-3 打ち上げ花火定理(R=0となるのは「打ち上げ花火系列」に限る、という主張。)につながります。定理2-3は1xn, 3xnのへやに帰着することで示す（残った(偶数,偶数)のマスが、半分サイズの部屋と全く同じ挙動を示す）（とくしんさんの方法）。
上で挙げられた上界通りの入れ方を具体的に構築し、最終決着する（ぶめぎゃ虫さん、栗林司さん）。また、入れ方が最低1通り存在するKinnxmにおいて、全ての黒マスがA面に入るパターンが存在することが示される（系3-1 市松存在定理）。
ノートは以上です。
角のへやや端のへやでも、同様の考え方を使うことが出来ます。A面を以下のように定義します。
角のへや…盤面の角と一致するマスを含む方
端のへや…盤面の辺に接するマス群(1xnマス)を多く含む方
角や端では、一般には定理1-3 ビショップの定理が成り立ちません。
角の19in10x5 (R=3*(25-19)-18=0)
条件を満たす唯一の黒マスの入れ方には、16個のB面の黒マスが存在します。B面に黒マスが入るのに余裕値が消費されていません。全ての黒マスがA面に入るパターンはありません（全てB面も無い）。
端の9in7x3（R=3*(11-9)-5=1）
これもAB面混在の唯一解です。余裕値が1残っており、これは「空中のへやではR>0のとき常に複数解である」事実と対照的です。
また、黒マスを最大限入れてR>=3となる例も多くあります。R>=3というところだけを見ると、黒マスをさらに1個増やしてもRが正ですが、実際にはその余裕値では足りないということになります。
空中のへやで「最大限入れてR>=3」となるのは、定理2-3 打ち上げ花火定理の主張のとおり、「nxmのへやでnとmが奇数であり、かつ打ち上げ花火型でも1xn,3xnでもないとき」に限ります。この証明も定理1-3 ビショップの定理が根幹となっているため、角や端のへやへの応用に難航しています→いました。ペナルティへやわけによって解決。空中のへやについては、具体的構築の章で、R>3となる例は存在しないことが示されますが、角や端のへやでは以下のようなR>=3となる例が存在します。 角の27in15x5（R=3*(38-27)-28=5)
R=5です。黒マス28個のときR=2ですが、解はありません。
角の(3 or 5 or 7 or 9)x7
端の5x(3 or 5 or 7 or 9), 16in7x6, 19in7x7, 32in12x7, 27in9x8, 31in9x9
すべてR=3です。
角の5xnについて、黒マスを最大限入れたときのRは、線形に増加します。角のへや_幅5