遊び方

ライツアウトは次の\(\,2\,\)つの無料サイトで遊べるので，遊んでみてください。

bubudoufu.com

よかひよかとき

ライツアウトは\(\,2\,\)元体\(\,\mathbb{F}_2\,\)を考えることで，線形代数的に解を計算できることが知られています。

しかし今回の記事ではグラフ理論の握手補題を用いることで，
全ライトがONの状態は消灯できることを示していきます。

線形代数的な解法については気が向いたら解説しようと思うので，私のやる気をあげるためにも要望を言っていただけると助かります。

全ライトがONの状態は消灯できる

この節ではグラフ理論の握手補題を用いて，次の定理1を示していきましょう。

ちなみに初期状態ですべてのライトがONでない場合，下図のようにこの定理が成り立たない配置があります。

この配置だとどこのライトを切り替えても片方がONで，もう片方がOFFの状態が繰り返されるので，定理は成り立ちません。

さてそれでは定理1の証明を行っていきましょう。

まずはライトの配置をグラフに対応させられることを説明しましょう。

与えられたライトの配置から

ライトをグラフの点，\(\,2\,\)つのライトが隣接しているとき，それらに対応する\(\,2\,\)点を辺で結ぶことで，グラフを構成することができます。

例えば\(\,3\times 3\,\)のライトでは次のようになります。

このようにライトの配置をグラフに対応させた考え方のもと証明を行っていきます。

※逆にグラフがライトの位置を表していると考えることもできます。

この場合，グラフの点をライトとみなしますが，必ずしも正方形のライトの配置に対応できるわけではありません(正方形のライトだと\(\,1\,\)つの正方形に\(\,4\,\)つまでしか正方形を隣接させられないから)。

まとめるとグラフ上でライツアウトを考えると，正方形のライトを超えた，“広義の”ライツアウトとなります。

一応，今回の証明はその広義のライツアウトでも正当性が保たれることを意識していただけると嬉しいです。

さてライトの配置をグラフに落とし込めることが分かりました。

この考え方で定理1をライトの数\(\,n\,\)に関する数学的帰納法で証明していきます。

まず\(\,n=1\,\)のとき，ONのライトが一つだけなので，そのライトを切り替えることで全体をOFFにできるので，定理は成り立ちます。

続いて\(\,n=k\in \mathbb{N}\,\)のとき定理は成り立つとして，\(\,n=k+1\,\)のときについて考えましょう。

\(n=k+1\,\)のときを背理法で示すために，

「初期状態ではすべてのライトがONなのに，\(\,(k+1)\,\)個のライトのある配置\(\,G\,\)では消灯できない」

と仮定しましょう。

このとき次の主張1を認めて良いことを確認しましょう。

分かりやすいように，
\(G\,\)が\(\,3\times 3\,\)のライトの配置だったとして考えると，次の図のような操作がそれぞれのライトに対して可能ということです。

主張1をなぜ認めて良いのかと言うと，

ライトの配置\(\,G\,\)において問題のライト\(\,v\,\)をないものとみなすと，\(\,k\,\)個のライトの配置になるので，

帰納法の仮定から\(\,v\,\)以外の\(\,k\,\)個のライトのON/OFFを反転できるような操作\(\,S_v\,\)を\(\,G\,\)に行えます。

この\(\,S_v\,\)を行ったとき，ライト\(\,v\,\)自身は反転しません。なぜなら反転してしまうとすると，\(\,G\,\)は消灯できないと仮定したことに矛盾してしまうからです。

よって主張1を認めても良いことが分かりました。

またさらに次の主張2も認めて良いです。

主張1で認められた操作\(\,S_u,S_v\,\)を続けて行うことで，操作\(\,S_{u,v}\,\)が実現できるので，主張2は認めても大丈夫です。

さらにさらに次の主張3も成り立ちます。

\(3\times 3\,\)の例で言えば次の図のようになります。

この操作\(\,T\,\)は全てのライトを\(\,1\,\)回ずつ切り替えることで実現されます。

なぜなら

奇数次のライト\(\,\to\,\)隣接するライト(奇数個)と自分自身の，合計偶数回ON/OFFが反転

偶数次のライト\(\,\to\,\)隣接するライト(偶数個)と自分自身の，合計奇数回ON/OFFが反転

となるからです。

そのため主張3は成り立ちます。

さてここまで示した主張1,2,3を使って\(\,G\,\)が消灯できることを示し，矛盾を導きましょう。

次のような手順を踏むことで，\(\,G\,\)は消灯できます。

この手順を実行する際に問題になるのが，\(\,(2)\,\)でペアを作ることができるのか？という点です。

これは握手補題(の系)より，奇数次のライトの個数は偶数個であることから保証されます。

したがって上のような手順により\(\,G\,\)が消灯できてしまい，これは\(\,G\,\)が消灯できないとしたことに矛盾します。

ゆえに背理法から\(\,n=k+1\,\)のときも定理が成り立つことが示されました。

以上より題意は示されました。\(\quad\square\)

今回の記事ではライツアウト(Lights Out)を解説いたしました。

握手補題だけで「全ライトがONの状態は消灯できる」ことを証明できるのは感動ですね。

ライツアウトを線形代数的に解析して得られる結果については，要望があれば解説するつもりなので，言っていただけると嬉しいです。

もし「説明がわかりにくい」などご要望・ご感想がありましたら，
X（旧:Twitter）で#トイカラでつぶやいていただけると，できる限り対応します。

ここまで読んでいただき，ありがとうございました。

• \([1]\) “ライツアウト”.bubudouf.com.https://bubudoufu.com/webapp/lights-out/.2025-03-20参照
• \([2]\) “点灯パズル自動解答（ライツアウト）”.よかひよかときhttps://yokatoki.sakura.ne.jp/gameland/TentouPuzzle1_JS/TentouPuzzle1_JS.cgi.2025-03-20参照