進捗

お久しぶりです。

先週から実家に帰省してて、十分な進捗を生むぞと意気込んでたんですが結局だらけてしまってうまくいきませんでした。

そのなかでも少しだけ考えてたことがあって、

グラフ理論の授業で出てきた(らしい)次のような問題

(全部スマホで書いてて、Texとか使ってないし、多分見直しもしないので見づらかったり間違えていたら言ってくれると嬉しいです)

「下図のような正方形のボタンを並べた装置を考える。この装置のボタンは赤色、または青色の光を発していて各ボタンを押すごとに、そのボタンと上下左右のボタンの光が反転する。

いま、初期状態は全てのボタンが青であるとするとき、ボタンの配置に関わらず全てのボタンを赤に反転させる事ができるか」

この問題、答えとしては「出来る」で証明(もどき)は次のような感じ

*ここで言うグラフとは、有限集合VとE⊂[V]^2 の組G＝(V,E)のこと。グラフの頂点集合をV(G)、頂点数を|V(G)|で表すこととして、u∈V(G)に対してuに繋がってる辺の数をuの次数と呼んで、uに辺で繋がってる頂点のことをuの隣接点と呼ぶことにします。

∵装置を下図のようなグラフGとみなし、頂点数に関する帰納法で示す.

 

|V(G)|＝1のとき明らか.

任意の自然数nに対して,|V(G)|<nでの成立を仮定する.

ここで,

＊ある|V(G)|＝nなるグラフGに関して、「出来ない」と仮定する.

いま,帰納法の仮定より任意のu∈V(G)に対してある操作SuでGからuを除いたグラフは全てのボタンを反転できる.

また,＊の下でGに対してSuを行ってもuは反転しない.つまり＊の下で次の主張を得る

ゴミ1

任意のu∈V(G)に対して,ある操作Suでu以外のボタンを全て反転させることができる.

また、これより次の主張も得る

ゴミ2

任意のu,v∈V(G)に対して,ある操作SuとSvを連続して行うことでuとvだけを反転させることができる.

(∵まずGに対してSuを行うとuを除いて全て反転,次にSvを行うとvはそのままで他は全て反転.

従ってvは反転したまま,uもSuで反転するのでこの二つだけが反転したことになる)

 

次にGにおいて,全てのボタンを押した後の色の変化を考えることで次の主張を得る

Claim

全てのボタンを押すと

①次数が奇数の点→元の色に戻る

②次数が偶数の点→反転する

(∵全てのボタンを押すと,各ボタンは次数(隣接する点の和 数)＋1(自分自身)回色が変わる.

従って①→偶数回反転して元に戻る

           ②→奇数回反転して、元と逆の色になる

)

以上より，＊の下次の手順で全ての色を反転させることができる

(1)全てのボタンを押す

(2)反転していない点を2頂点ずつの組みに分ける*

(3)ゴミ2よりそれぞれの組みだけ反転させていくことで、全て反転する

従って|V(G)|＝nの時成立より、＊は矛盾.

帰納法より任意のnで出来る.

□

*(2)で、反転していない点を全て2頂点ずつに分けれる(次数が奇数の点は必ず偶数個)というのは任意の空でないグラフに対して言えることで、気になる人は 握手補題とかで調べてみて下さい。

少し面白くないですか？この議論

成立しないと仮定すると成立しちゃうってことですよね(帰納法の仮定も効いてる)

 この問題で背理法を除いてみようと思ってここ数日少しだけ考えてたんですが、なかなかうまくいきませんでした。

多分原因は「下図のようなグラフを考える」みたいなところで議論を誤魔化してる所で、もう少しちゃんとグラフの言葉にしてあげないといけないなかな、と。

(そうしないと厳密に証明できたとは言えないし)

どうにか出来ないかもう少し考えてみることにします(できたらまたここで報告させてください)