超へやわけＭＸ
2003-01-27 Asaokitan
(2008-12-08 修正)
もどる
§０ 導入
へやわけにおいて、ある大きさの部屋に入る黒マスの最大数をＭＸ値と呼びます。たとえば ２×２ の部屋のＭＸ値は ２ で、３×３ の部屋のＭＸ値は ５ です。ここではＭＸ値の一般解と、その求め方について説明します。
今回は僕の独力ではなく、にゃんこばずうかさん、孔明さん、とくしんさん、ぶめぎゃ虫さん、栗林司さんなどとの協同によるものです。にゃんこばずうかさんのページの掲示板、およびメールでのやりとりがあって初めて可能になりました。Special Thanks to みんな、です。以下、本文中で他の方の名前や、他の方による用語を借りさせていただいている箇所があります。
にゃんこばずうかさんのページへ
ニコリ公式パズルガイド「へやわけ」 - Webニコリ
ＭＸ値を求めるJavascript（孔明さん作）
ではさっそくＭＸ値の一般解にまいりましょう。
MX値の一般解
１×ｎ の場合
ｎ＝奇数のとき （ｎ＋１）／２
ｎ＝偶数のとき ｎ／２
３×ｎ の場合
３×（４ｋ−１） のとき ５ｋ
３×（４ｋ） のとき ５ｋ
３×（４ｋ＋１） のとき ５ｋ＋２
３×（４ｋ＋２） のとき ５ｋ＋３
その他（ｎ×ｍ）の場合
（２＾ｋ−１）×（２＾ｋ−１） のとき （ｎｍ＋ｎ＋ｍ）／３
その他の 奇数×奇数 のとき （ｎｍ＋ｎ＋ｍ）／３ 未満の最大の整数
偶数×偶数、偶数×奇数のとき （ｎｍ＋ｎ＋ｍ−２）／３ を超えない最大の整数
つまり
５×５の部屋なら （５×５＋５＋５）／３＝１１．６…だから １１個
５００×８００ の部屋なら（４０００００＋１３００−２）／３＝１３万３７６６個
の黒マスが入るが、次の１個はどう頑張っても入らない、ということです。
以下、その説明に入ります。
§１ 準備
まず、証明に重要な役割を果たすしまつぶし理論の基本的な道具立てをします。
定理1-1 （しまつぶし原理）
白マスと黒マスに塗り分けられた任意の盤面について、ある黒マスを白マスに変えることで減少するシマ（黒マスに囲まれて孤立した白マス群）の数は、最大３個である。
これはあるマスに隣接するマスは最大４個であり、その４個が全て別のシマに属していたとして、減少するシマが３個であることから明らかです。
ここで、ある部屋を次のように市松模様に塗り分けることを考えます。
＋−−−−−−−＋
｜■ ■ ■ ■｜
｜ ■ ■ ■ ｜
｜■ ■ ■ ■｜
｜ ■ ■ ■ ｜
｜■ ■ ■ ■｜
＋−−−−−−−＋
市松模様の片方を「Ａ面」、もう片方を「Ｂ面」と呼ぶことにします。偶数部屋（面積が偶数）の場合はＡ面・Ｂ面に区別がありませんが、奇数部屋の場合には、数が１つ多い方（隅を含む方）をＡ面とすることにします。
さて、上の図の黒マスの数（つまり、Ａ面の面積）を
Ａ 、上の図で発生しているシマ（元ジマ）の数を
Ｓ とおくと、しまつぶし原理より次が言えます。
定理1-2 （しまつぶし第一公式）
ある部屋にＫ個の黒マスが入っているとき、Ｒ（余裕値）を
Ｒ ＝ ３（Ａ − Ｋ）−Ｓ
とおくと、Ｒ≧０。
上の図で黒マスをＫ個まで減らす場合、消せる黒マスは
Ａ−Ｋ 個ですから、それによって解消できるシマの数は、最大
３（Ａ−Ｋ） 個です。これが元ジマの個数より少ないとハタンですから、Ｒ≧０
が言えます。
シマ３−ｒ個しか減少させないで黒マスを減少させることを「余裕値Ｒをｒだけ消費する」と言います。具体的に市松模様から黒マスを減らしていくとき、余裕値の消費量の合計を
Ｒ 未満に抑えることが必要になります（これを「しまつぶし規則」と呼びます）。
ここで、次の定理を示します。
定理1-3 （ビショップの定理）
奇数部屋のＢ面に黒マスが入っているならば、Ｒ＞０。
これを証明します。
まず、部屋の境界線はないものとして考えます。
Ｂ面に入っている黒マスが１つだけであったとします。
Ｓ
ＳＡＳ
ＳＡＢＡＳ
ＳＡＳ
Ｓ
Ｂ が黒とすると、Ａ面の黒マスが４つ減らざるを得ません。そのとき減るシマは８個です。黒マスは計３つ減ったにもかかわらず、シマの減少は８個ですから、余裕値を消費してしまっていることが分かります。
Ｂ面に複数の黒マスが入っている場合は、斜めにひとつながりになっている黒マスの集まりを考えます。黒マスの連鎖は輪っかになってはいけませんから、黒マスの斜めに黒マスをくっつける、という作業を繰り返すことによってその形は必ず作ることができます。
ある黒マスの斜めの位置に黒マスを置いたとき、上図におけるＡのうち２つは既に消えていますから、「Ｂ面に黒マスが１増加」「Ａ面に黒マスが２減少」となり、黒マス減少は１つだけで済みます。しかし、Ｓ
のうち少なくとも ６つは既に消えていますから、シマの減少は最大でも
３つです。
したがって、上図のＢに黒マスを連鎖させていっても、シマの減少数が黒マスの減少の３倍を超えることはできず、Ｒを消費してしまうことに変わりがないことが分かります。（なお、Ｂ面の黒マスが連続しておらず、離れていた場合は、さらに
Ｒ を消費してしまうだけです。）
次に部屋の境界線が関係する場合を考えます。
Ｂ｜ＡＳ
｜Ｓ
Ｓ｜
｜
Ｂ｜ＡＳ
Ｓ Ｂ ｜Ｓ
―――――＋
ＳＡＳ
Ｓ
図のような位置を境界線が通っている場合、Ａ
が外に飛び出しているので、黒マスの減少数が少なくなります。しかし、必ず対応して
Ｓ も ３ つ以上はみ出していることが分かります（ここで隅のマスはＢ面に属さないということが重要です）。したがって部屋の境界線が関与しても、やはりシマの減少数が黒マスの減少の３倍に達することはできません。
以上より、奇数部屋のＢ面に黒マスがあった場合は、Ｒ
を消費せざるを得ない （Ｒ＞０） ことが示されました。
ここで特殊な場合について、先にＭＸ値を出しておきます。
廊下（１×ｎ）のＭＸ値は
奇数部屋のとき （ｎ＋１）／２
偶数部屋のとき ｎ／２
大通り（３×ｎ）のＭＸ値は
３×（４ｎ−１） のとき ５ｎ
３×（４ｎ） のとき ５ｎ
３×（４ｎ＋１） のとき ５ｎ＋２
３×（４ｎ＋２） のとき ５ｎ＋３
である。
廊下については明らかです。
大通りについては、部屋を分割して各部屋ごとのＭＸ値から考える方法（分割充填理論）で示します。
＋−−−−＋−−−−＋−−−
｜ ｜ ｜
｜ ｜ ｜
｜ ｜ ｜
＋−−−−＋−−−−＋−−−
部屋のサイズが ３×（４ｎ） の場合、３×４のＭＸ値は
５ ですから、３×４ｎ のＭＸ値は ５ｎ 以下です。しかしサザンクロス（５
in ３×３）を順に詰めていけば ５ｎ 個入ることは明らかですから、ＭＸ値＝５ｎ
であることが分かります。
その他の場合も同様にＭＸ値を求めることができます。
この廊下と大通りは特殊なので、§２以降ではあらかじめ除外して考えます。
§２ 展開
まず、しまつぶし第一公式よりすぐに次が言えます。
定理2-1 （とくしんの定理）
ｎ×ｍ の部屋について、Ｔ（とくしん数）を
奇数部屋のとき Ｔ ＝ （ｎｍ＋ｎ＋ｍ）／３
偶数部屋のとき Ｔ ＝ （ｎｍ＋ｎ＋ｍ−２）／３
とおくと、ＭＸ値 ≦ Ｔ 。
しまつぶし第一公式より
３（Ａ−Ｋ）−Ｓ ≧ ０
ですから、
Ｋ ≦ （３Ａ−Ｓ）／３
となります。部屋を ｎ×ｍ とすれば、Ａ（Ａ面のマス数）と Ｓ（元ジマ数）は ｎ、ｍ で表せますから、代入して計算すると
奇数部屋 ： ＭＸ値 ≦ （ｎｍ＋ｎ＋ｍ）／３
偶数部屋 ： ＭＸ値 ≦ （ｎｍ＋ｎ＋ｍ−２）／３
となり、定理が示されます。
次に、奇数部屋ではほとんどの場合、等号は成り立たないことを示すため、まず次の補題を準備します。
補題2-2 （奇数交点の補題）
奇数部屋で Ｒ＝０ のとき、座標が（奇数，奇数）のマスは全て黒。
Ｒ＝０ であれば、定理1-3（ビショップの定理）よりＢ面側に黒マスが入ることはなく、外周の消費量ゼロでないマスは必ず黒です。このとき、（奇数，奇数）のマスが白であったと仮定します。
＋―――――――――――――――＋
｜■ ■ ■ ■ ■ ■ ■ ■｜
｜ ■ ｒ ｒ ｒ ｒ ｒ ■ ｜
｜■ ■｜
｜ ｒ ｑ ｑ ｒ ｜
｜■ ｐ ■｜
｜ ｒ ｑ ｑ ｒ ｜
｜■ ■｜
｜ ｒ ｒ ｜
｜■ ■｜
｜ ｒ ｒ ｜
｜■ ■｜
｜ ｒ ｒ ｜
｜■ ■｜
｜ ■ ｒ ｒ ｒ ｒ ｒ ■ ｜
｜■ ■ ■ ■ ■ ■ ■ ■｜
＋―――――――――――――――＋
仮に ｐ が白であったとすると、その斜めに位置する ｑ のマスは消費量がプラスになるため、黒と確定します。したがって、ｐ の上下左右に位置する （奇数，奇数）のマスのどれかが白であることになります。この議論を繰り返すと、ｐ とつながったＡ面の白マスは全て （奇数，奇数） であり、（偶数，偶数） のマスはないことになります。しかし ｒ のマスは全て （偶数，偶数） ですから、ｐ を含む白マス連続はこの部屋の中でシマになってしまうことが分かります。
したがって、Ｒ＝０ とすると （奇数，奇数） の交点は全て黒であることが分かります。
定理2-3 （打ち上げ花火定理）
奇数部屋で Ｒ＝０ が成立するのは、２＾ｎ−１マス四方（打ち上げ花火系列）の場合のみである。
mod ４ で分類して示します。
ｉ） タテ、ヨコ どちらかが ４ｎ＋１ マスの場合
｜ ｜
｜■ ■ ■ ■ ■ ■ ■ ■ ■｜
｜ ａ ｂ ｃ ｄ ｅ ｆ ｇ ｈ ｜
｜■ ■ ■ ■ ■ ■ ■ ■ ■｜
＋−−−−−−−−−−−−−−−−−＋
Ｒ＝０とすると補題2-2 より、（奇数，奇数）は全て黒です。ここで、端から２列目の（偶数，偶数）のマスに注目します。
Ｒ＝０ ですから、しまつぶし規則により ａ
は黒、したがって分断禁により ｂ は白です。すると、再びしまつぶし規則が使えて、ｃ
は黒、ｄ は白…と繰り返されることが分かります。ところが、この位置にくるマスの数は
２ｎ 個（偶数）ですから、最後のマスが白になり、しまつぶし規則に違反してしまうことが分かります。したがって、４ｎ＋１マスの辺があった場合、Ｒ＝０
は成り立ちません。
ｉｉ） （４ｎ−１）×（４ｍ−１） マスの場合
同じく（奇数，奇数）は全て黒です。
＋―――――――――――――――＋
｜■ ■ ■ ■ ■ ■ ■ ■｜
｜ ｜
｜■ ■ ■ ■ ■ ■ ■ ■｜
｜ ｜
｜■ ■ ■ ■ ■ ■ ■ ■｜
｜ ｜
｜■ ■ ■ ■ ■ ■ ■ ■｜
｜ ｜
｜■ ■ ■ ■ ■ ■ ■ ■｜
｜ ｜
｜■ ■ ■ ■ ■ ■ ■ ■｜
｜ ｜
｜■ ■ ■ ■ ■ ■ ■ ■｜
｜ ｜
｜■ ■ ■ ■ ■ ■ ■ ■｜
＋―――――――――――――――＋
ここで、残った（偶数，偶数）のマスに着目すると、これは７×７の部屋における黒マスとまったく同じ振る舞いをすることが分かります（とくしんさんの方法）。一般には
（４ｎ−１）×（４ｍ−１） で Ｒ＝０ が可能 ⇔
（２ｎ−１）×（２ｍ−１） でも可能
が成立します。
（２ｎ−１）×（２ｍ−１） もまた奇数部屋ですから、その部屋にもまたとくしんさんの方法が適用でき、上と組み合わせると
（４ｎ−１）×（４ｍ−１） で Ｒ＝０ が可能 ⇔
（ｎ−１）×（ｍ−１） でも可能
が言えます。ここで ｎ または ｍ が奇数とすると、ｎ が奇数のとき ２ｎ−１ ≡ １ （mod ４） ですから、（２ｎ−１）×（２ｍ−１） は既に見た ｉ） の場合であることになり、Ｒ＝０ は成立せず、矛盾が生じます。したがって ｎ と ｍ はともに偶数であり、（ｎ−１）×（ｍ−１） も奇数部屋であることが分かります。
この議論を繰り返すことにより、次々と小さい奇数部屋がつくられ、タテかヨコの一方が ３マス にまで縮まったサイズに必ず辿り着きます。ここで大通り（３×ｎ）の市松模様は
＋−−−−−−−−−−−−
｜■ ■ ■ ■ ■ ■
｜ ■ ■ ■ ■ ■
｜■ ■ ■ ■ ■ ■
＋−−−−−−−−−−−−
であり、長辺≧４ の場合、シマがありますが、消費量ゼロのマスは存在しないことが分かります。したがって Ｒ＝０ とできるのは ３×３ の場合のみであり、結局、奇数部屋で Ｒ＝０ にできるのは、縮小を繰り返してサザンクロス ３×３ に行き着く場合に限られることが分かります。
したがって、これを逆にたどると、
３×３ で可能
ｋ×ｋ で可能 ⇔ （２ｋ＋１）×（２ｋ＋１）で可能
ということですから、一般には （２＾ｎ−１）×（２＾ｎ−１）の場合に可能であり、またこの場合に限られることが示されました。
以上より、
打ち上げ花火系列 ＭＸ値 ＝ Ｔ
その他の奇数部屋 ＭＸ値 ＜ Ｔ
偶数部屋 ＭＸ値 ≦ Ｔ
であることが分かりました。（Ｔはとくしん数）
次節で、上記による最大値が実際のＭＸ値であることを示します。
§３ 決着
以下はほぼ全て、ぶめぎゃ虫さんと栗林司さんによる成果です。ぶめぎゃ虫さんの描いた図を使わせてもらっています。
打ち上げ花火系列については既にＭＸ値が確定していますので、これを除外します。
次が示せればＭＸ値がひとつに確定し、最終決着が図られることになります。
奇数部屋のとき Ｒ≦３
偶数部屋のとき Ｒ＜３
i) 偶数×偶数のとき
２×ｎ、４×ｎ、６×ｎ でＲ＜３とできることは容易に示せます。ｍ×ｎ でＲ＜３が可能だったとすると、下図のように付け加えれば、（ｍ＋６）×（ｎ＋６）でも可能なので、帰納的に全ての場合で可能であることが分かります。
■□■□■□■□■□■□■□■□■□
□■□■□■□■□■□■□■□□□■
■□□□□□□□□□□□□□■□■□
□■□■□■□■□■□■□■□□□■
■□□□■□■□■□■□■□■□■□
□■□■□□□□□□□□□□□□□■
■□□□■□■□■□■□■□■□■□
□■□■□■□■□■□■□■□■□■
ii) 偶数×奇数 のとき
ｍ×ｎ のときＲ＜３とすると、下図のように付け加えれば、（ｍ＋３）×（ｎ＋３）でもＲ＜３なので、やはり帰納的に全ての場合でＲ＜３とできることが分かります。
■□■□■□■□■□■□■□■□■□
□■□■□■□■□■□■□■□■□■
■□□□□□□□□□□□□□□□□□
□■□■□■□■□■□■□■□■□■
■□□□■□■□□□■□■□□□■□
□■□■□□□■□■□□□■□■□□
■□■□■□■□■□■□■□■□■□
以上より、全ての偶数部屋において Ｒ＜３ がいえました。
奇数部屋に移ります。奇数では mod ６ で分類して考えます。
i) タテ、ヨコどちらかが ６ｎ＋５ のとき
この場合は、下図のような配置が常に可能であり、Ｒを消費しているのは色付きマスの ２ だけですから、［Ｔ］（端数切り捨て）＝ＭＸ値が確定します。
■□■□■□■□■□■□■□■□■
□■□■□■□■□■□□□■□■□
■□□□□□□□□□■□■□□□□
□■□■□■□■□■□□□■□■□
■□□□■□■□□□■□■□□□■
□■□■□□□■□■□□□■□■□ ↑２マスずつ反復可能
■□□□■□■□□□■□■□□□■ ↓
□■□■□□□■□■□■□■□■□
■□□□■□■□□□□□□□□□■
□■□■□□□■□■□■□■□■□
■□■□■□■□■□■□■□■□■
←−−−−→
６マスずつ反復可能
ii) （６ｎ＋１）×（６ｍ＋３）のとき
この場合はＲを消費しているのは色付きマスの１ だけですから、やはり ［Ｔ］＝ＭＸ値です。
■□■□■□■□■□■□■□■□■□■
□■□■□■□■□■□□□■□□□■□
■□□□□□□□□□■□■□□□■□■
□■□■□■□■□■□□□■□■□□□
■□□□■□■□□□■□■□□□■□■ ｜ ６マスずつ反復可能
□■□■□□□■□■□■□■□■□■□
■□□□■□■□□□□□□□□□□□■
□■□■□□□■□■□■□■□■□■□
■□■□■□■□■□■□■□■□■□■
←−−−−→
６マスずつ反復可能
ｉｉｉ） （６ｎ＋１）×（６ｍ＋１）のとき
このとき Ｔ（とくしん数）を計算すると整数になっています。
したがって、定理2-3（打ち上げ花火定理）より、打ち上げ花火系列のときは
ＭＸ値＝Ｔ、そうでないときは ＭＸ値＜Ｔ です。後者の場合、以下のように配置すれば、Ｒの消費は色付きマスの左が１、右が２で合計３で済んでいますから、ＭＸ値＝Ｔ−１です。
■□■□■□■□■□■□■□■□■□■
□■□■□■□■□■□□□■□■□■□
■□□□□□□□□□■□■□□□□□■
□■□■□■□■□■□□□■□■□■□
■□□□■□■□□□■□■□□□■□■
□■□■□□□■□■□□□■□■□□□
■□□□■□■□□□■□■□□□■□■ ｜ ６マスずつ反復可能
□■□■□□□■□■□□□■□■□■□
■□□□■□■□□□■□■□□□□□■
□■□■□□□■□■□■□■□■□■□
■□□□■□■□□□□□□□□□□□□
□■□■□□□■□■□■□■□■□■□
■□■□■□■□■□■□■□■□■□■
←−−−−→
６マスずつ反復可能
ｉv） （６ｎ＋3）×（６ｍ＋3）のとき
このときも ３Ｔ≡０ （mod ３）です。
したがって打ち上げ花火系列でなければＭＸ値＜Ｔです。このときは下図のように配置すればやはり
ＭＸ値＝Ｔ−１ とすることができます。
■□■□■□■□■□■□■□■□■□■□■
□■□■□■□■□■□□□■□■□■□■□
■□□□□□□□□□■□■□□□□□□□■
□■□■□■□■□■□□□■□■□■□■□
■□□□■□■□□□■□■□□□■□■□■
□■□■□□□■□■□□□■□■□□□□□
■□□□■□■□□□■□■□□□■□■□■
□■□■□□□■□■□□□■□■□■□■□ ｜ ６マスずつ反復可能
■□□□■□■□□□■□■□□□□□□□■
□■□■□□□■□■□□□■□■□■□■□
■□□□■□■□□□■□■□□□■□■□■
□■□■□□□■□■□■□■□■□□□□□
■□□□■□■□□□□□□□□□■□■□■
□■□■□□□■□■□■□■□□□□□■□
■□■□■□■□■□■□■□■□■□■□■
←−−−−→
６マスずつ反復可能
以上により全てのパターンが網羅され、３Ｔ≡１or２ （mod ３） のときは Ｒ＜３ 、３Ｔ≡０ （mod ３） のときは Ｒ≦３ であることが分かりました。３Ｔ≡０ のときは Ｒ＝０ ではありませんから、これで奇数部屋についても全ての場合についてＭＸ値が確定しました。
また以上により、ぶめぎゃ虫さんが予想した次の定理が言えます。
系3-1 （市松存在定理）
任意の Ｋ in ｎ×ｍ について、全ての黒マスがＡ面に入るパターンが存在する。
以上まとめると
偶数部屋 Ｔ を超えない最大の整数
打ち上げ花火系列 Ｔ
その他 Ｔ 未満の最大の整数
となり、先に解いた廊下と大通りの場合を合わせ、これで全て解決しました。
おめでと〜！！