超へやわけMX


2003-01-27 Asaokitan
(2008-12-08 修正)

もどる


 §0 導入

 へやわけにおいて、ある大きさの部屋に入る黒マスの最大数をMX値と呼びます。たとえば 2×2 の部屋のMX値は 2 で、3×3 の部屋のMX値は 5 です。ここではMX値の一般解と、その求め方について説明します。

 今回は僕の独力ではなく、にゃんこばずうかさん、孔明さん、とくしんさん、ぶめぎゃ虫さん、栗林司さんなどとの協同によるものです。にゃんこばずうかさんのページの掲示板、およびメールでのやりとりがあって初めて可能になりました。Special Thanks to みんな、です。以下、本文中で他の方の名前や、他の方による用語を借りさせていただいている箇所があります。

 にゃんこばずうかさんのページへ
 ニコリ公式パズルガイド「へやわけ」 - Webニコリ

 MX値を求めるJavascript(孔明さん作)

 ではさっそくMX値の一般解にまいりましょう。


MX値の一般解

 1×n の場合

n=奇数のとき (n+1)/2
n=偶数のとき n/2

 3×n の場合

3×(4k−1) のとき 5k
3×(4k) のとき 5k
3×(4k+1) のとき 5k+2
3×(4k+2) のとき 5k+3

 その他(n×m)の場合

(2^k−1)×(2^k−1) のとき (nm+n+m)/3
その他の 奇数×奇数 のとき (nm+n+m)/3 未満の最大の整数
偶数×偶数、偶数×奇数のとき (nm+n+m−2)/3 を超えない最大の整数

 つまり

5×5の部屋なら (5×5+5+5)/3=11.6…だから 11個
500×800 の部屋なら(400000+1300−2)/3=13万3766個

 の黒マスが入るが、次の1個はどう頑張っても入らない、ということです。

 以下、その説明に入ります。


 §1 準備

 まず、証明に重要な役割を果たすしまつぶし理論の基本的な道具立てをします。


定理1-1 (しまつぶし原理)
 白マスと黒マスに塗り分けられた任意の盤面について、ある黒マスを白マスに変えることで減少するシマ(黒マスに囲まれて孤立した白マス群)の数は、最大3個である。


 これはあるマスに隣接するマスは最大4個であり、その4個が全て別のシマに属していたとして、減少するシマが3個であることから明らかです。

 ここで、ある部屋を次のように市松模様に塗り分けることを考えます。

+−−−−−−−+
|■ ■ ■ ■|
| ■ ■ ■ |
|■ ■ ■ ■|
| ■ ■ ■ |
|■ ■ ■ ■|
+−−−−−−−+

 市松模様の片方を「A面」、もう片方を「B面」と呼ぶことにします。偶数部屋(面積が偶数)の場合はA面・B面に区別がありませんが、奇数部屋の場合には、数が1つ多い方(隅を含む方)をA面とすることにします。
 さて、上の図の黒マスの数(つまり、A面の面積)を A 、上の図で発生しているシマ(元ジマ)の数を S とおくと、しまつぶし原理より次が言えます。


定理1-2 (しまつぶし第一公式
 ある部屋にK個の黒マスが入っているとき、R(余裕値)を

R = 3(A − K)−S

 とおくと、R≧0。


 上の図で黒マスをK個まで減らす場合、消せる黒マスは A−K 個ですから、それによって解消できるシマの数は、最大 3(A−K) 個です。これが元ジマの個数より少ないとハタンですから、R≧0 が言えます。
 シマ3−r個しか減少させないで黒マスを減少させることを「余裕値Rをrだけ消費する」と言います。具体的に市松模様から黒マスを減らしていくとき、余裕値の消費量の合計を R 未満に抑えることが必要になります(これを「しまつぶし規則」と呼びます)。
 ここで、次の定理を示します。


定理1-3 (ビショップの定理
 奇数部屋のB面に黒マスが入っているならば、R>0。


 これを証明します。

 まず、部屋の境界線はないものとして考えます。
 B面に入っている黒マスが1つだけであったとします。

  S
 SAS
SABAS
 SAS
  S
 

 B が黒とすると、A面の黒マスが4つ減らざるを得ません。そのとき減るシマは8個です。黒マスは計3つ減ったにもかかわらず、シマの減少は8個ですから、余裕値を消費してしまっていることが分かります。

 B面に複数の黒マスが入っている場合は、斜めにひとつながりになっている黒マスの集まりを考えます。黒マスの連鎖は輪っかになってはいけませんから、黒マスの斜めに黒マスをくっつける、という作業を繰り返すことによってその形は必ず作ることができます。
 ある黒マスの斜めの位置に黒マスを置いたとき、上図におけるAのうち2つは既に消えていますから、「B面に黒マスが1増加」「A面に黒マスが2減少」となり、黒マス減少は1つだけで済みます。しかし、S のうち少なくとも 6つは既に消えていますから、シマの減少は最大でも 3つです。
 したがって、上図のBに黒マスを連鎖させていっても、シマの減少数が黒マスの減少の3倍を超えることはできず、Rを消費してしまうことに変わりがないことが分かります。(なお、B面の黒マスが連続しておらず、離れていた場合は、さらに R を消費してしまうだけです。)
 次に部屋の境界線が関係する場合を考えます。

     B|AS
      |S
     S|
      |
     B|AS
  S B |S
 ―――――+
   SAS
    S

 図のような位置を境界線が通っている場合、A が外に飛び出しているので、黒マスの減少数が少なくなります。しかし、必ず対応して S も 3 つ以上はみ出していることが分かります(ここで隅のマスはB面に属さないということが重要です)。したがって部屋の境界線が関与しても、やはりシマの減少数が黒マスの減少の3倍に達することはできません。
 以上より、奇数部屋のB面に黒マスがあった場合は、R を消費せざるを得ない (R>0) ことが示されました。

 ここで特殊な場合について、先にMX値を出しておきます。


定理1-4 (廊下と大通りのMX値)

 廊下(1×n)のMX値は

奇数部屋のとき (n+1)/2
偶数部屋のとき n/2

 大通り(3×n)のMX値は

3×(4n−1) のとき 5n
3×(4n) のとき 5n
3×(4n+1) のとき 5n+2
3×(4n+2) のとき 5n+3

 である。


 廊下については明らかです。
 大通りについては、部屋を分割して各部屋ごとのMX値から考える方法(分割充填理論)で示します。

+−−−−+−−−−+−−−
|    |    |
|    |    |
|    |    |
+−−−−+−−−−+−−−

 部屋のサイズが 3×(4n) の場合、3×4のMX値は 5 ですから、3×4n のMX値は 5n 以下です。しかしサザンクロス(5 in 3×3)を順に詰めていけば 5n 個入ることは明らかですから、MX値=5n であることが分かります。
 その他の場合も同様にMX値を求めることができます。

 この廊下と大通りは特殊なので、§2以降ではあらかじめ除外して考えます。


 §2 展開

 まず、しまつぶし第一公式よりすぐに次が言えます。


定理2-1 (とくしんの定理
 n×m の部屋について、T(とくしん数)を

奇数部屋のとき T = (nm+n+m)/3
偶数部屋のとき T = (nm+n+m−2)/3

 とおくと、MX値 ≦ T 。


 しまつぶし第一公式より

3(A−K)−S ≧ 0

 ですから、

K ≦ (3A−S)/3

 となります。部屋を n×m とすれば、A(A面のマス数)と S(元ジマ数)は n、m で表せますから、代入して計算すると

奇数部屋 : MX値 ≦ (nm+n+m)/3
偶数部屋 : MX値 ≦ (nm+n+m−2)/3

 となり、定理が示されます。

 次に、奇数部屋ではほとんどの場合、等号は成り立たないことを示すため、まず次の補題を準備します。


補題2-2 (奇数交点の補題)
 奇数部屋で R=0 のとき、座標が(奇数,奇数)のマスは全て黒。


 R=0 であれば、定理1-3(ビショップの定理)よりB面側に黒マスが入ることはなく、外周の消費量ゼロでないマスは必ず黒です。このとき、(奇数,奇数)のマスが白であったと仮定します。

+―――――――――――――――+
|■ ■ ■ ■ ■ ■ ■ ■|
| ■ r r r r r ■ |
|■             ■|
| r q q       r |
|■   p         ■|
| r q q       r |
|■             ■|
| r           r |
|■             ■|
| r           r |
|■             ■|
| r           r |
|■             ■|
| ■ r r r r r ■ |
|■ ■ ■ ■ ■ ■ ■ ■|
+―――――――――――――――+

 仮に p が白であったとすると、その斜めに位置する q のマスは消費量がプラスになるため、黒と確定します。したがって、p の上下左右に位置する (奇数,奇数)のマスのどれかが白であることになります。この議論を繰り返すと、p とつながったA面の白マスは全て (奇数,奇数) であり、(偶数,偶数) のマスはないことになります。しかし r のマスは全て (偶数,偶数) ですから、p を含む白マス連続はこの部屋の中でシマになってしまうことが分かります。

 したがって、R=0 とすると (奇数,奇数) の交点は全て黒であることが分かります。


定理2-3 (打ち上げ花火定理)
 奇数部屋で R=0 が成立するのは、2^n−1マス四方(打ち上げ花火系列)の場合のみである。


 mod 4 で分類して示します。

 i) タテ、ヨコ どちらかが 4n+1 マスの場合

|                 |
|■ ■ ■ ■ ■ ■ ■ ■ ■|
| a b c d e f g h |
|■ ■ ■ ■ ■ ■ ■ ■ ■|
+−−−−−−−−−−−−−−−−−+

 R=0とすると補題2-2 より、(奇数,奇数)は全て黒です。ここで、端から2列目の(偶数,偶数)のマスに注目します。
 R=0 ですから、しまつぶし規則により a は黒、したがって分断禁により b は白です。すると、再びしまつぶし規則が使えて、c は黒、d は白…と繰り返されることが分かります。ところが、この位置にくるマスの数は 2n 個(偶数)ですから、最後のマスが白になり、しまつぶし規則に違反してしまうことが分かります。したがって、4n+1マスの辺があった場合、R=0 は成り立ちません。

 ii) (4n−1)×(4m−1) マスの場合

 同じく(奇数,奇数)は全て黒です。

+―――――――――――――――+
|■ ■ ■ ■ ■ ■ ■ ■|
|               |
|■ ■ ■ ■ ■ ■ ■ ■|
|               |
|■ ■ ■ ■ ■ ■ ■ ■|
|               |
|■ ■ ■ ■ ■ ■ ■ ■|
|               |
|■ ■ ■ ■ ■ ■ ■ ■|
|               |
|■ ■ ■ ■ ■ ■ ■ ■|
|               |
|■ ■ ■ ■ ■ ■ ■ ■|
|               |
|■ ■ ■ ■ ■ ■ ■ ■|
+―――――――――――――――+

 ここで、残った(偶数,偶数)のマスに着目すると、これは7×7の部屋における黒マスとまったく同じ振る舞いをすることが分かります(とくしんさんの方法)。一般には

(4n−1)×(4m−1) で R=0 が可能 ⇔
  (2n−1)×(2m−1) でも可能

 が成立します。
 (2n−1)×(2m−1) もまた奇数部屋ですから、その部屋にもまたとくしんさんの方法が適用でき、上と組み合わせると

(4n−1)×(4m−1) で R=0 が可能 ⇔
  (n−1)×(m−1) でも可能

 が言えます。ここで n または m が奇数とすると、n が奇数のとき 2n−1 ≡ 1 (mod 4) ですから、(2n−1)×(2m−1) は既に見た i) の場合であることになり、R=0 は成立せず、矛盾が生じます。したがって n と m はともに偶数であり、(n−1)×(m−1) も奇数部屋であることが分かります。

 この議論を繰り返すことにより、次々と小さい奇数部屋がつくられ、タテかヨコの一方が 3マス にまで縮まったサイズに必ず辿り着きます。ここで大通り(3×n)の市松模様は

+−−−−−−−−−−−−
|■ ■ ■ ■ ■ ■
| ■ ■ ■ ■ ■
|■ ■ ■ ■ ■ ■
+−−−−−−−−−−−−

 であり、長辺≧4 の場合、シマがありますが、消費量ゼロのマスは存在しないことが分かります。したがって R=0 とできるのは 3×3 の場合のみであり、結局、奇数部屋で R=0 にできるのは、縮小を繰り返してサザンクロス 3×3 に行き着く場合に限られることが分かります。

 したがって、これを逆にたどると、

3×3 で可能
k×k で可能 ⇔ (2k+1)×(2k+1)で可能

 ということですから、一般には (2^n−1)×(2^n−1)の場合に可能であり、またこの場合に限られることが示されました。

 以上より、

打ち上げ花火系列 MX値 = T
その他の奇数部屋 MX値 < T
偶数部屋 MX値 ≦ T

 であることが分かりました。(Tはとくしん数)
 次節で、上記による最大値が実際のMX値であることを示します。


 §3 決着

 以下はほぼ全て、ぶめぎゃ虫さんと栗林司さんによる成果です。ぶめぎゃ虫さんの描いた図を使わせてもらっています。

 打ち上げ花火系列については既にMX値が確定していますので、これを除外します。
 次が示せればMX値がひとつに確定し、最終決着が図られることになります。

奇数部屋のとき R≦3
偶数部屋のとき R<3

 i)  偶数×偶数のとき

 2×n、4×n、6×n でR<3とできることは容易に示せます。m×n でR<3が可能だったとすると、下図のように付け加えれば、(m+6)×(n+6)でも可能なので、帰納的に全ての場合で可能であることが分かります。

■□■□■□■□■□■□■□■□■□
□■□■□■□■□■□■□■□□□■
■□□□□□□□□□□□□□■□■□
□■□■□■□■□■□■□■□□□■
■□□□■□■□■□■□■□■□■□
□■□■□□□□□□□□□□□□□■
■□□□■□
■□■□■□■□■□■□
□■□■□■□■□■□■□■□■□■

 ii)  偶数×奇数 のとき

 m×n のときR<3とすると、下図のように付け加えれば、(m+3)×(n+3)でもR<3なので、やはり帰納的に全ての場合でR<3とできることが分かります。

■□■□■□■□■□■□■□■□■□
□■□■□■□■□■□■□■□■□■
■□□□□□□□□□□□□□□□□□
□■□
■□■□■□■□■□■□■□■
■□□□■□■□□□■□■□□□■□
□■□■□□□■□■□□□■□■□□
■□■□■□■□■□■□■□■□■□

 以上より、全ての偶数部屋において R<3 がいえました。


 奇数部屋に移ります。奇数では mod 6 で分類して考えます。

 i)  タテ、ヨコどちらかが 6n+5 のとき

 この場合は、下図のような配置が常に可能であり、Rを消費しているのは色付きマスの 2 だけですから、[T](端数切り捨て)=MX値が確定します。

■□■□■□■□■□■□■□■□■
□■□■□■□■□■□□□■□■□
■□□□□□□□□□■□■□□□
□■□■□■□■□■□□□■□■□
■□□□■□■□□□■□■□□□■
□■□■□□□■□■□□□■□■□ ↑2マスずつ反復可能
■□□□■□■□□□■□■□□□■ ↓
□■□■□□□■□■□■□■□■□
■□□□■□■□□□□□□□□□■
□■□■□□□■□■□■□■□■□
■□■□■□■□■□■□■□■□■

   ←−−−−→
   6マスずつ反復可能

 ii)  (6n+1)×(6m+3)のとき

 この場合はRを消費しているのは色付きマスの1 だけですから、やはり [T]=MX値です。

■□■□■□■□■□■□■□■□■□■
□■□■□■□■□■□□□■□□■□
■□□□□□□□□□■□■□□□■□■
□■□■□■□■□■□□□■□■□□□
■□□□■□■□□□■□■□□□■□■ | 6マスずつ反復可能
□■□■□□□■□■□■□■□■□■□
■□□□■□■□□□□□□□□□□□■
□■□■□□□■□■□■□■□■□■□
■□■□■□■□■□■□■□■□■□■

   ←−−−−→
   6マスずつ反復可能

 iii) (6n+1)×(6m+1)のとき

 このとき T(とくしん数)を計算すると整数になっています。
 したがって、定理2-3(打ち上げ花火定理)より、打ち上げ花火系列のときは MX値=T、そうでないときは MX値<T です。後者の場合、以下のように配置すれば、Rの消費は色付きマスの左が1、右が2で合計3で済んでいますから、MX値=T−1です。

■□■□■□■□■□■□■□■□■□■
□■□■□■□■□■□□□■□■□■□
■□□□□□□□□□■□■□□□□□■
□■□■□■□■□■□□□■□■□■□
■□□□■□■□□□■□■□□□■□■
□■□■□□□■□■□□□■□■□□□
■□□□■□■□□□■□■□□□■□■ | 6マスずつ反復可能
□■□■□□□■□■□□□■□■□■□
■□□□■□■□□□■□■□□□□□■
□■□■□□□■□■□■□■□■□■□
■□□□■□■□□□□□□□□□
□■□■□□□■□■□■□■□■□■□
■□■□■□■□■□■□■□■□■□■

   ←−−−−→
   6マスずつ反復可能

 iv) (6n+3)×(6m+3)のとき

 このときも 3T≡0 (mod 3)です。
 したがって打ち上げ花火系列でなければMX値<Tです。このときは下図のように配置すればやはり MX値=T−1 とすることができます。

■□■□■□■□■□■□■□■□■□■□■
□■□■□■□■□■□□□■□■□■□■□
■□□□□□□□□□■□■□□□□□□□■
□■□■□■□■□■□□□■□■□■□■□
■□□□■□■□□□■□■□□□■□■□■
□■□■□□□■□■□□□■□■□□□□□
■□□□■□■□□□■□■□□□■□■□■
□■□■□□□■□■□□□■□■□■□■□ | 6マスずつ反復可能
■□□□■□■□□□■□■□□□□□□□■
□■□■□□□■□■□□□■□■□■□■□
■□□□■□■□□□■□■□□□■□■□■
□■□■□□□■□■□■□■□■□□□□□
■□□□■□■□□□□□□□□□■□■□■
□■□■□□□■□■□■□■□□■□
■□■□■□■□■□■□■□■□■□■□■

   ←−−−−→
   6マスずつ反復可能

 以上により全てのパターンが網羅され、3T≡1or2 (mod 3) のときは R<3 、3T≡0 (mod 3) のときは R≦3 であることが分かりました。3T≡0 のときは R=0 ではありませんから、これで奇数部屋についても全ての場合についてMX値が確定しました。

 また以上により、ぶめぎゃ虫さんが予想した次の定理が言えます。


系3-1 (市松存在定理)
 任意の K in n×m について、全ての黒マスがA面に入るパターンが存在する。


 以上まとめると

偶数部屋 T を超えない最大の整数
打ち上げ花火系列 T
その他 T 未満の最大の整数

 となり、先に解いた廊下と大通りの場合を合わせ、これで全て解決しました。

 おめでと〜!!


もどる