長方形グリッドのσゲーム

第2章では一般グラフ上のσゲームについて考察した．第3章では，本来のライツアウトパズルの形に戻って，｛，、におけるライツアウトパズルを考える．長方形のグリッドみ，、において，m，ηがどんな条件を満たせば，σゲ］ムのルールで任意の状態から全ての頂点をOの状態にできる

のかを調べていく．

3．1 凡，、上の特性写像

この章では，第2章と同様に0pm，皿を考えて，状態や操作を0pm，、の元で表す、以下，0pm，皿を簡単に0m，肌と表すことにする．第2章ではグラフG

の頂点にj頃番をつけることにより，0GをF2弁γ内のベクトルと対応させて考えたが，第3章では以下の方法によって0m，、の元を別の形で捉える．

凡，肌の上から乞番目，左からゴ番目の頂点を（台，ゴ）と表す。すると，ん，、

の頂点集合は｛1，…，m｝X｛1，…，η｝となり，！∈0m，、＝mαρ（γF2）はプ：｛1，…，m｝X｛1，…，η｝→F2となる．このとき，プを

・一

i∴∴）1｝）

という行列Xと対応させると，この写像は1F2土の線型写像で，0m，几と Mm，、（F2）との間の全単射となる．したがってこの対応はF2土のベクトル空間の同型である．以下，この章では0m，、の元を上記のように行列と同一視することする、この同一視では，全ての頂点がOとなる状態は零行列0

で表される．

定義3・1．1σ：0m，帆→0m，刊を次のように定める。0m，肌竺Mm，几（1F2）の元 λ＝（α｛ゴ）に対して，0m，肌皇Mm，、（F2）の元B＝（6｛ゴ）を

〜＝α1j＋α1−1，ゴ十α1。・，j＋α1，卜・十α1，ゴ・1∈F・

第3章長方形グリッドのσゲーム ⁵²

とし，σ（λ）＝Bとする．ただし，αoゴ，αm＋1，ゴ，α40，α｛，、十1はOとする．この対

応が線型写像となることは容易に確かめられる．

定理3・1・20m，、竺Mm，れ（lF2）の元X，γに対して，状態X＝（〜）に操作 γ＝（吻）を加えた状態x ＝（叱）は

X ＝X＋σ（γ）

となる．

証明 σゲーム上では，頂点κ幻の操作後の状態｛は，操作前の状態と，頂点（乞，ゴ）を押すかどうか及び，頂点（乞，ゴ）に隣接している頂点をいくつ押すかで決まってくるので，各頂点に対して

幻＝均ゴ十挑，ゴ十吻一1，j＋眺十1，1＋挑，j−1＋眺，ゴ十／

が成り立つ．ただし，蛎，μm＋15，腕，挑，、十1はOである、したがって，X ＝

X＋σ（γ）である． □ 定理3．1．2と定理2．3．3を比べると，定義3．1．1で定めた写像σはσゲーム

における特性写像と同じ性質をもっていることが分かる．実際，定義2．3．4 では0GをF2弁γと同一視して特性写像σを考えたが，この定義3．1，1のσ は0p柵，、をMm，冊（1F2）と同一視して特性写像を書き下したものとなっている．よって，この定義3，1．1のσをPm，机上のσゲームの特性写像と呼ぶことにする．

グラフみ，η上の特性写像をσとすると，状態0からある状態Xに，適当な操作γを加えて変化することが可能であるということは，0＋σ（γ）＝X

となることと同値である．よって，状態0からある状態Xに，適当な操作 γを加えて変化することが可能であるための必要十分条件は，XがImσ の元であることである．

定義3．1．3み，冊上のσゲームにおいて，任意の状態Xにある操作γを加えて状態0への遷移が可能であるとき，み，ηはσ可移であるというこ

とにする．

定理3．1．4グラフPm，机上の特性写像をσとする．このとき，以下は同値

である．

1，dim（Kerσ）＝Oである。

第3章長方形グリッドのσゲーム ⁵³ 2．み，冗はσ可移である．

証明 2．の，0m，。皇M肌，帆（F2）の任意の元Xに対して，0からXにできるという二とは，0m，、≧Mm，、（F2）の任意の元Xに対して，ある操作γ があって，σ（γ）＝Xを満たすことと同値である．つまりImσが0m，、全体となることと同値である。ゆえにdim（Cm，帆トdim（Imσ）であり，定理 1．3．5より，dim（Kerσ）＝0であることと同値である．口定理3．1．5グラフみ，帆上の特性写像をσとする。dim（Kerσ）＝dとすると，以下が成り立つ．

1・σゲームの操作で状態0から遷移できるXの個数は0岬全体のフ

2m几

で1ア個である・

2．状態0から遷移できるようなXに対し，0をXに移す操作γの個

数は2d個である．

証明まず1．を示す。まず，dim（0m，仰）＝㎜ηである．dim（Kerσ）＝dなので，定理L3，5より，dim（Imσ）＝mn＿dである．ゆえに，Imσの元の個 2mη

数は2㎜■d＝＿個である．

2d

次に21を示す．状態0から状態XできるようなXに対して，0をXに

移す操作γ∈0m，几は，0＋σ（γ）＝Xとなるようなγの総数である．こ

こで，0をXに移す操作の1つを㍉とすると，σ（篶）＝Xである．ηに

ある操作zを加えて

σ（y乙十Z）＝X （3．1）

となるような操作Zについて調べる．σは線型写像なので，式（3．1）は σ（η）十σ（Z）＝Xと同値である．σ（巧）＝Xなので，これはσ（Z）＝0を意味する。つまりZはKerσの元である。よって，集合｛η十Z−Z∈Kerσ｝

が，σ（γ）＝Xとなるγ全体である．以上より，状態0を状態Xに移すような操作γの個数はdim（Kerσ）＝dより，2d個である． □ 定理3．1．4及び3．1．5から，σゲームにおいては，Kerσの次元が分かれ

ば，状態0から状態Xに変化できないようなXがあるかどうか，また何

通りの操作があるかが分かることになる1

そこで，第3章の次節以降では，Kerσの次元を調べることを目標とする、

第3章長方形グリッドのσゲーム 54

3．2 Kerσについて

定義3．2．1λm∈Mm（1F2）を以下のような行列とする．

0100．．．000 1010．．．OO0 0101．．．000

λm＝

0000．．．010 0000．1．101 0000．．．010

定理3．2．2σをみ，、上のσゲームの特性写像とする．このとき，0m，、竺 Mm，η（lF2）の元Xに対して，

σ（X）＝λmX＋Xん十X

が成り立つ．

証明 X∈M m，兀（F2）について，λmXは，

0100．．．000 1010．．．000

〃一 P1∵：（∴）

0000．．．101 0000．．．010

と表されるので，λmx＝B＝（δ｛ゴ）とすると，わ幻成分は z1ゴ

うザ（0…01010…0） 1ゴ＝ル1，ゴ十叫・，ゴ

剛