正方形のライツアウトパズルについて，常に可解かどうかの考察(自作問題の解説)

　 先日投稿した問題 の解説をしとうございます．

下にスクロールすると解説が始まります．
↓
↓
↓

解説

　まず問題の設定を確認しましょう．
ひとまず$n=3$で考えてみます．
$n=3$のときの初期状態の例
$n=3$のときの盤面を1つ持ってきました．$a_{2,3}$に操作を行ってみます．$a_{2,4}$は存在しない(盤面の外)ので，$a_{2,3},a_{1,3},a_{2,2},a_{3,3}$の白黒を反転させます．
$a_{2,3}$への操作
こんな具合で複数のマス目に操作を行ってすべてのマスを白色にしていきます．

このようなパズルは，「 ライツアウト 」という名前がついているそうです．タメになったね～

ちなみに，この初期配置だと，$a_{1,3},a_{2,1},a_{2,2},a_{3,2},a_{3,3}$の5つのマスに操作を行うことで，盤面のすべてのマスを白色にすることができます．よって，この初期配置は良い配置です．
操作を行う順番は関係なく，同じマスに対して2回操作を行うことは，そのマスに対して操作を行っていないことと同値です．

　唐突ではありますが$n\times n$の盤面が与えられたとき，黒で塗られたマスを1，白で塗られたマスを0とすれば，盤面1つ1つに対して，${\mathbb{F}}_2$上の$n^2$次元ベクトルを一意に定めることができます．
例えば，図1の配置は，$$\left(\begin{array}{c}1\\ 0\\ 1\\ 0\\ 1\\ 1\\ 0\\ 1\\ 0\end{array}\right)$$
とすることができます．
さらに，盤面の各マスに対する操作は，色を反転させるマスに対応する成分を$1$としてそれ以外を$0$にした$n^2$次ベクトルを足す${\mathbb{F}}_2$上の演算と定められます．
例えば，図2の操作は，
$$\left(\begin{array}{c}1\\ 0\\ 1\\ 0\\ 1\\ 1\\ 0\\ 1\\ 0\end{array}\right)+\left(\begin{array}{c}0\\ 0\\ 1\\ 0\\ 1\\ 1\\ 0\\ 0\\ 1\end{array}\right)=\left(\begin{array}{c}1\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ 1\\ 1\end{array}\right)$$
となり，確かに対応することが分かります．
盤面の初期配置に対応するベクトルを$\mathit{a}$，盤面の各マス$a_{1,1},a_{1,2},\cdots ,a_{1,n},a_{2,1},\cdots ,a_{n,n-1},a_{n,n}$に対する操作を表すベクトルをそれぞれ${\mathit{a}}_{1,1},{\mathit{a}}_{1,2},\cdots ,{\mathit{a}}_{1,n},{\mathit{a}}_{2,1},\cdots ,{\mathit{a}}_{n,n-1},{\mathit{a}}_{n,n}$とすると，
与えられた盤面に対して，どのマスに対して操作を行えば良いかは，$b_{i,j}(0\le i,j\le n,b_{i,j}\in \{0,1\})$として，有限体${\mathbb{F}}_2$上での方程式
$$\mathit{a}+\sum _{0\le i,j\le n}{b}_{i,j}{\mathit{a}}_{i,j}=\mathbf{0}$$
を$b_{i,j}$について解く問題に帰着できます．(多分)

この連立方程式の解が一意に定まることは，操作に対応するベクトルを並べた${\mathrm{LM}}_{n^2}({\mathbb{F}}_2)$である行列
$$\mathit{A}=\left(\begin{array}{cccccccc}{\mathit{a}}_{1,1}& {\mathit{a}}_{1,2}& \cdots & {\mathit{a}}_{1,n}& {\mathit{a}}_{2,1}& \cdots & {\mathit{a}}_{n,n-1}& {\mathit{a}}_{n,n}\end{array}\right)$$
が正則であることと同値です．

$\mathit{A}$が正則であるかを調べるために，行列式を求めてみます．($\left|\mathit{A}\right|\in {\mathbb{F}}_2$であることに注意．)
あるマスに対する操作を表すベクトルを考えると，隣り合うマスを表す成分が$1$となり，$\mathit{A}$を構成するベクトルは，左上のマスから順番に並べているため，$\mathit{A}$は対称行列となりますね．
例えば，$n=3$のとき，
$$\mathit{A}=\left(\begin{array}{ccccccccc}1& 1& 0& 1& 0& 0& 0& 0& 0\\ 1& 1& 1& 0& 1& 0& 0& 0& 0\\ 0& 1& 1& 0& 0& 1& 0& 0& 0\\ 1& 0& 0& 1& 1& 0& 1& 0& 0\\ 0& 1& 0& 1& 1& 1& 0& 1& 0\\ 0& 0& 1& 0& 1& 1& 0& 0& 1\\ 0& 0& 0& 1& 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 1& 0& 1& 1& 1\\ 0& 0& 0& 0& 0& 1& 0& 1& 1\end{array}\right)$$
であるため，確かに対称行列となっています．
定義から行列式を計算することを考えます．
$n$次対照群を$S_n$，$\mathit{A}$の$(i,j)$成分を$\mathit{A}(i,j)$，置換を$\sigma$で表すと，
$$\left|\mathit{A}\right|=\sum _{\sigma \in S_{n^2}}\prod _{i=1}^{n^2}\mathit{A}(i,\sigma (i))$$です．
$\left|\mathit{A}\right|\in {\mathbb{F}}_2$であるため，置換の符号については考える必要はありません．
よって，$\mathit{A}$の成分から，行と列が重複しないように$1$を選ぶ方法の個数を調べることで行列式を求められます．
また，対称行列であることから，対角成分に対して非対称な成分の選び方が偶数通り存在するため，対称な成分の選び方の個数の偶奇を調べるだけでOKです．
この選び方を定める$S_n$の置換全体の集合を$T_n$とします．

　ここで，少し天下り的ではありますが次の問題を考えます．

上から$i$行目，左から$j$行目のマスを$b_{i,j}$とします．
また，あるタイルに対して，タイルが配置されている$2$つのマスの組を$(b_{i,j},b_{i\pm 1,j\pm 1})$と表します．
例えば，$n=3$のとき，タイルの置き方の例を下に示します．
タイルの置き方の一例
この置き方は$(b_{2,2},b_{2,3}),(b_{2,1},b_{3,1})$と書くことができます．
置き方$(b_{2,2},b_{2,3}),(b_{2,1},b_{3,1})$に対して，$\sigma \in S_{3^2}=S_9$を，
$$\left(\begin{array}{ccccccccc}1& 2& 3& 4& 5& 6& 7& 8& 9\\ 1& 2& 3& 7& 6& 5& 4& 8& 9\end{array}\right)$$と定めると，これは$\mathit{A}$の対角成分に対して対称な成分の選び方です．
一般に，$(b_{i,j},b_{u,v})$にタイルを置いたとき，$n(i-1)+j$と$n(u-1)+v$を入れ替えるような$\sigma$を定めると
実はこのタイルの敷き詰め方一つ一つに対して，対応する置換$\sigma \in T_{n^2}$が一意に定まります！
よって，$|\mathit{A}|$はこのようなタイルの置き方の方法の個数の偶奇を調べることで求めることができますね．

$n$が奇数のときを考えます．${\displaystyle \frac{n+1}{2}}$列目に対して非対称な置き方に対して，左右反転させた置き方が存在するため，非対称な置き方全体の個数は偶数個です．
以下では左右対称な置き方の個数を考えます，
$(b_{i,\frac{n+1}{2}},b_{i,\frac{n+1}{2}\pm 1})$のような置き方は左右非対称であるため，${\displaystyle \frac{n+1}{2}}$列目をまたぐような置き方は考えません．
よって，${\displaystyle \frac{n+1}{2}}$列目上のタイルの置き方と，それ以外の部分でのタイルの置き方に分けて数えればOKですね．
${\displaystyle \frac{n+1}{2}}$列目上のタイルの置き方についてですが，これは$1\times n$の盤面にタイルを置くことと同じです．この置き方の個数を$F_n$とし，$F_{n-1}$と$F_{n-2}$を考えることで，
$$\{\begin{array}{l}{F}_1=1\\ F_2=2\\ F_{n+2}=F_{n+1}+F_n\end{array}$$
という漸化式が成り立ちますね．(この辺は有名問題なのでざっくりいきます)
見るからにこれはフィボナッチ数列です．($F_0=1,F_1=1$とした場合のもの)
フィボナッチ数の有名事実として，次が成り立ちます．
$$2|F_n⟹n\equiv 2(mod3)$$
$n$が奇数であることとあわせて，$n=6k-1$のときは，${\displaystyle \frac{n+1}{2}}$列目上のタイルの置き方を考えた時点で，タイルの置き方の個数が偶数通りであることが確定します．よって，$|\mathit{A}|=0$であり，$\mathit{A}$は正則ではありません．そのため，$n=6k-1$のときのライツアウトについて，良い配置ではないものが存在します．
例えば，$n=5$のとき，下のライツアウトは，どのように操作を行ったとしても，解くことができません．
$n=5$のときの可解でない盤面の例

次に，${\displaystyle \frac{n+1}{2}}$列目のタイルの置き方の個数が奇数個であるような$n$について考えます．
まず，$n=1$の場合ですが，あきらかに置き方の個数は$1$通りです．
$n=3$の場合を考えます．このとき，盤面は真ん中の十字部分と$4$つの$1\times 1$の盤面に分けることができます．$1\times 1$の盤面についてはタイルの置き方が奇数通り，$1\times 3$の部分については$n\not\equiv 2(mod3)$であるため，置き方は奇数通りです．よって，$n=3$の盤面も置き方は奇数通りです．
$n=3$のとき，4つの正方形と十字の盤面に分けて考えられる．

このような要領で，$n=1$からスタートして，
$n\times n$の盤面$4$つと，$1\times n$の盤面$2$つと，$1\times (2n+1)$の盤面を用いて$(2n+1)\times (2n+1)$の盤面を帰納的に作ったとき，一辺の長さは$2^k-1$で表されます．$2^k-1\not\equiv 2(mod3)$なので，全ての$k$に対して$n=2^k-1$の盤面のタイルの配置の方法は奇数通りです．
そのため，$\mathit{A}$は正則であり，$n=2^k-1$のときのライツアウトは，つねに良い配置となります．
$7\times 7$の盤面は，$3\times 3$の盤面$4$つと$1\times 3$の盤面$2$つと，$1\times 7$の盤面を用いて分解できる．
今の議論は，$n$を奇数として盤面の分解を考えました．そのため，$1$辺の長さが偶数マスのときは，上記の分解は行えません．
構成する最小の盤面を$1\times 1$として考えましたが，例えば$4\times 4$のときはどうなるでしょうか．つまり，$1$辺の長さは
$$\{\begin{array}{l}{c}_1=4\\ c_{n+1}=2c_n+1\end{array}$$
で表される数列($c_n=5\times 2^n-1$です)に含まれています．

$n=c_k$のとき，先ほどの分解を進めると，$4\times 4$の盤面が現れるため，$n=4$のタイルの置き方を考えます．例によって，左右対称かつ回転対称な置き方しか考えないため，考えられる配置は以下の$2$通りだけです！
すべての対称なタイルの置き方(これ以外の置き方は反転や回転によって一致する偶数個の組みができます)
よって，$n=4$の場合は，タイルの置き方は偶数個であって，$\mathit{A}$は正則ではありません．そのため$n=4$のライツアウトについて，良い配置ではないものが存在します！

$n=c_k$のときは，盤面の分解を繰り返すと$4\times 4$の盤面が表れて，この置き方が偶数通りであるため，$n=c_k=5\times 2^k-1$すべてについて，$\mathit{A}$は正則ではありません．そのため，この場合ライツアウトに良い配置でないものが存在します．

解説おわり

いかがでしたか？(書くのつかれた...)(読むのも疲れたと思います)

読みづらい文章であったと思いますが，ここまで読んでくださりありがとうございました．
シンプルなパズルから線形代数につながって，タイルの置き方の組み合わせの議論にまで話が広がるのが面白かったです．
なお，上の文章を読むと分かりますが，$n$が偶数であるときはまだ結論を出せていません．この方法だと上手くいかないのかもしれない...ごにょごにょ...

以下余談になります．
私はこれについて半年近く考えて上の結論を出したのですが，
ここまでウッキウキで書き終わってから，この記事とほぼ同じ内容の動画が見つかりました(既出だった)
そちらの方が$100$億倍分かりやすかったので，そちらの視聴をお勧めします．(参考文献に載せました)(先駆者様ごめんなさい．)

ライツアウト部分を取っ払うと，線形代数が不要になり，単純にタイルの敷き詰め方の個数の偶奇を求める問題になります．
この部分をうまいこと改変してOMC用の問題が作れるんじゃないかという安直な考えのもと作問をして，没にした問題を最後に掲載して終わりたいと思います．

気持ち悪いですね～

じゃあね～