【詳しい人は】クロススイッチ問題【教えてくれ】

今回は、僕が『クロススイッチ問題』と（勝手に）呼んでいるものについてお話しします。
（分量：１０分程度）

ゲーム　『クロススイッチ』

ルールは簡単！

まずは例題で、確認と腕試しといきましょう。

例題
4-直線スイッチの図
これは、スイッチが4個横並びになっている様子を表しています。
そして、真ん中にある二つの黄色くなっているのはスイッチが光っている、つまりこれらのスイッチが【on】の状態になっており、左右の端それぞれにある白くなっているのは、スイッチが【off】の状態を表しています。

ここで、この図の左端のスイッチからA,B,C,Dと記号をつけ、【on】のスイッチを１、【off】のスイッチを０と数字で表すとすると、上の図は
A:0 , B:1 , C:1 , D:0
となります。
4-直線スイッチの図（記号あり）

これを縮めて、　0110　と表すことにしましょう。
これで上の図の様子を0110と数字の列で表すことができました。これからはこの数列を使っていきましょう！

ではこれからスイッチを押していきます。まず一番左、Aのスイッチを押すと、スイッチ達には次のような変化が起こります。
A:0 →　A:1
B:1 →　B:0
まず、押されたAのスイッチ自身が切り替わり、【off】から【on】になりました。そして、Aと隣り合っているBのスイッチも切り替わり、【on】から【off】となりました。C,DのスイッチはAのスイッチとは隣り合っていないので、変化はありません。
この変化により、スイッチ達の状態が、0110 から1010に変わりました。

4-直線スイッチ、Push A

さて、今のスイッチ達の状態は1010です。ここでPush Cを行うことで、スイッチ達は1101に変化します。

ここまでで、Push A,Push Cと続けて行いましたが、これらの操作をまとめて、Push ACと呼ぶのでした。つまり、Push AC　により、スイッチ達は、0110から1101に変化したといえます。

4-直線スイッチ、Push A、Push C
このまま、他のスイッチも押してみて、すべてのスイッチを光らせてみましょう！Push AC と押して、0110から1101となりました。ここから、どのスイッチを押せばいいでしょうか？
・
・
・
・

ここまでをまとめると、スイッチははじめ0110の状態でしたが、
スイッチをA,C,B,Aの順に押すと（すなわち、Push ACBA と操作すると）、1111となりスイッチをすべて光らすことができました。
4-直線スイッチ、Push A、Push C、Push B,Push A

ここで問題

次は、上とは違う図の問題に挑戦してみましょう！
以下の二つの図のスイッチ達は、どのように押せばすべて光らせることができるでしょうか？

（1）
8-ループ図

（2）

1-直線、4-ループ図

『クロススイッチ問題』への準備

ここまではパズルの問題でしたが、これから数学らしい議論をしていきます。
まずはPush の性質から見てみましょう。

同じスイッチを2回押すと、そのスイッチ自身と、これとつながっているスイッチ達の各々が変化し、それ以外のスイッチは変化しません。
変化するスイッチはそれぞれ、
最初が1とすると、　1 → 0 → 1　と変化し、
最初が0とすると、　0 → 1 → 0　と変化します。

すなわち、スイッチを押す前と状態が変わらないので、どのスイッチも押さない操作と一致します。
よって、この操作を行ったときの変化は、全くスイッチを押さない操作と一緒になるので、この命題が成立します。

Push AB＝Push BA

この命題は、スイッチ達を次の４つのグループに分けて考えていきます。
〈１〉スイッチA,Bのどちらともつながっていないスイッチのグループ
〈２〉スイッチAとは隣り合っているが、Bとは隣り合っていないスイッチ
　　　のグループ
〈３〉スイッチBとは隣り合っているが、Aとは隣り合っていないスイッチ
　　　のグループ
〈４〉スイッチA,Bのどちらとも隣り合っているスイッチのグループ

命題1、命題2、命題3より次の定理が成立します。

この定理から、スイッチの押し方によるスイッチ達の状態の変化の仕方は有限であるといえます。

最初の例では、4つのスイッチA,B,C,Dが登場しました。これらの押し方は、まず以下の１6通りがあります。

これら16通り以外の操作をしようとしても、定理４よりスイッチを押す順番を変えて、同じスイッチを2回押す操作を押さない操作に置き換えることを繰り返すと、上の16通りのいずれかになります。
（上の囲いの中には、A,B,C,Dを重複なしで選ぶ場合（$2^4$=16通り)がすべて書き並べている。）

このように、各スイッチの押し方と、それによるスイッチの変化の仕方を数字で表すと、下の表のようになります。

この表を見ると、同じ変化の仕方をする異なるPushがないことが分かります。よって、スイッチ達の状態の変化の仕方はPushの場合の数と同じ16通りあることが分かります。

このスイッチ達がとることができる変化の仕方を表す変化数列は、以下の16通りになります。

ここで注目するポイントは、変化数列の集まりと表示数列の集まりのどちらも、1と0を重複を許して4つ並べたものをすべて含む集合であり、それ以外は含まないものになっていることです。
これより、ある表示数列で表されるスイッチ達に対して、すべてを光らせることができるような変化数列が存在することが言えます。

これらの話より、スイッチが一直線上に4つ並んだ図の場合、スイッチ達がどのような状態であってもそこからすべてのスイッチ達を光らせることができるような操作が必ず存在することが分かります。

変化数列と表示数列の対応の例

『クロススイッチ問題』　本題

・・・これを見ていると、スイッチが一直線上に４つ並んだ図以外のどんな並び方でも** 表示数列 の数と 操作数列 の数は一致しそうな気がしてきます。
例えば問（1）の並び方でも、表を作ってみるとスイッチ達の変化の仕方に被っているものはありません。（確かめてみて！）つまり、この並び方ではスイッチの状態がどんな場合でも必ずすべてを光らせる操作が存在します。**

それでは、問（2）の並び方の場合だとどうでしょう？対応表を作ってみると、次のようになります。
1-直線、4-ループ型の図（記号あり）

1-直線、4-ループ型の対応表

・・・見たところ、違う押し方なのに、全く同じ変化になる押し方のペアがいくつかあるようです。
(例えば、Push BC とPush ABDE はともにすべてのスイッチが【on】になる押し方になっている。すなわち、Push BC = Push ABDE )
つまりこの図の場合は、表示数列の数と操作数列の数が違うことになります。これは、はじめのスイッチ達の状態によっては、すべてを光らせることができる操作が存在しないことを表しています。
実際、下の図のような状態の場合は、どうスイッチを押してもすべてを光らせることができません。
1-直線、4-ループ型スイッチ（無理パターン）

さあ、ここで起こる疑問が今回のメインテーマである、『クロススイッチ問題』です。
まずは用語の定義から参りましょう。

つながり方が完全であれば、そのスイッチ図はどのような状態でもパズルに正解が存在することになります。できることなら、図をぱっと見ただけで完全か不完全かが見分けることができればいいなと思うのです。

実際にすべての操作を試して判断することもできますが、
どのような要素が完全・不完全を分けるのか?
がこの問題のポイントとなります。

まだ予想の範囲内ですが例えば、

• 左右対称なつながり方なら完全なのではないか？
• ループがたくさんあるつながり方は不完全になるのでは？
• 方程式を作れば判断できるのではないか？
• 幾何学の知識がつかえるのでは？
  ・・・等々あるでしょう。

もしかしたら、すでにこの問題に答えが存在しているにもかかわらず、深く調べもしない自分が勝手に悦に浸っているのかもしれません。
この問題の答えは既にあるぞ！というご意見がありましたら、ぜひお教えください。

知りたいことがもう一つ

さらに、『クロススイッチ問題』に関連してある予想があります。

4-直線スイッチ、8-ループスイッチの図（プレーン）

例えば、例として登場した上の二つの図は完全なつながりでした。
スイッチ達がどんな状態でも、すべてを【on】にする押し方があるので、上の定義よりFullになる押し方も存在します。

（一つ目は Push AD 、二つ目は Push ABCDEFGH がFullになる押し方。）

このように完全なつながりに対しては自明なのですが、重要なのは不完全な図にたいしても成り立つのではないかということです。

1-直線、4-ループ型の図（Full）

例で確認した、不完全な図である上のスイッチ達でも、
Push BC または　Push ABDE
という操作がFullになる押し方になります。

この予想は、
完全なつながり方をするスイッチ達だけでなく、全ての不完全なつながり方をするスイッチ達に対しても、Fullになる押し方が必ず存在するのではないか
ということを言っています。
スイッチ達のすべての変化を確認していけば、答えが分かるのかもしれませんが、スイッチの数がより多く複雑につながっているものになると、単なるごり押しではFullになる押し方を見つけることが難しくなるように思います。
どうにか、この予想を肯定的に示すか、一つ反例を見つけてしまうかしたいのですが、どちらもとても大変そうです。

〆

現在は、クロススイッチ問題と予想の解決方法をやみくもに探しているところです。もし、反例や証明、または既に解決済みだという情報がありましたら、数学見習いの私にご教授願えないでしょうか・・・。

追記：
参考文献があるといいよ、とのことなのでここで提示した予想と全く同じことを考えている日本語の論文がありましたので、ここに追加いたします！