MX値の上界に関する議論――余裕値について

超へやわけMX(外部サイト)(2019/3/31 Yahoo!ジオシティーズのサービス終了により公開終了)では、空中のへやにおけるMX値の一般解が求められ(2003/1/27~2008/12/8)、証明も示されています。以下の文章は、証明の鍵となる「余裕値」の登場までの説明です。原文を転載したものではありませんが、アイデアや定理はサイトの著者である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 奇数交点定理、定理2-3 打ち上げ花火定理)。定理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面混在の唯一解です。空中のへやで唯一解なのが全て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です。

手筋集トップへ戻る




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