電球スイッチの奇妙な設定(問題)

　鏡の国の博物館に白の騎士の奇妙で風変わりな発明品がまた1つ加わったという噂を耳にし，アリスはヤマネやその姪たちと連れ立って，どんなものかと見学にやって来た。博物館では白の騎士がご満悦の顔で一行を迎える。自ら自慢の工夫を語ろうという魂胆が丸見えだ。

　「今度の発明品は？」とヤマネが見ると，自分がかつて電球を点灯させるのに苦労したスイッチつき回転テーブル（2016年1月号「回転テーブルとスイッチ」）に似ていないこともない。テーブルに10個の電球が並び，それらがテーブルの端のスイッチにつながっている。

　白の騎士が説明する。「スイッチも電球もたくさんありますが，1つのスイッチが1つの電球に1対1に対応するようにはなっていません。どのスイッチもいくつかの電球のオン・オフ状態をまとめて切り替えることができるように設定できます。例えば，1つのスイッチで10個すべての電球の状態を一斉に切り替えるようにすることもできます。では，なぜスイッチがたくさんあるのかというと，1つだけでは同じ電球のセットを一斉に切り替えることしかできないので，複数のスイッチ操作を組み合わせることによっていろいろな点灯パターンを作れるようにしてあるというわけです」（下図参照）。

　「フーン」と感心したアリスが「では，どんな点灯パターンでも作れるのですか？」と問うと，白の騎士は「それはスイッチの設定次第ですな」と言う。「例えば，スイッチが2つだけでは4パターンしか作れないのは自明でしょう。それに，スイッチがたくさんあっても設定がうまくないと，当然作れないパターンが生じます」。そして，さも自慢げな顔で「幸い，いまはすべてのパターンが作れるように各スイッチが設定されていますので大丈夫です」と言う。

　すると，サンデイが 「じゃあ，電球に番号がついていますけど，奇数番の1，3，5，7，9だけを点灯させることもいまの設定でできるんですね。やってみてもらえますか？」と言う。具体的な要求が来たのは初めてらしく，白の騎士はたじたじとなり， 「ちょっとお待ちを……」と言ったきり考え込んでしまった。なかなか実演してくれないので，業を煮やした見学者たちが「本当にできるんですか？　1つの点灯パターンを作るのにそんなに考え込まねばならないのでは，電球とスイッチが1対1に対応していたほうが簡単じゃないかしら」と問い詰めると，白の騎士は 「いや，1個以上のどんな電球のセットに対しても，一連のスイッチ操作をうまくやれば，その中の奇数個の電球の状態を変えられることを確認してあるので，大丈夫なはずなのですが……」と言い訳する。

　「ええっ？」とアリス。「そんな変な条件が満たされていると，どうしてすべてのパターンが作れるのかしら？　さっぱりわからないわ。それより1番から10番までの各電球のオンとオフを単独で切り替えるための操作の表でも作っておけば，よほど役に立つでしょうに」。

　確かに，単独切り替え操作表はいろいろな点灯パターンを作るために実際にどのような操作をすればよいかを考えるうえで有用であろうが，実は白の騎士の発言も誤りではない。読者には，白の騎士が言った条件が満たされているなら，どんなパターンも必ず作れることを証明していただきたい。

　白の騎士が言った条件はちょっと複雑なので，念のために確認しておこう。1個以上からなる電球の任意のセットに対して一連のスイッチ操作がなにがしかあって，それによってセットの中の奇数個の電球の状態が切り替わるというものだ。ただし，セット外の電球については，その操作によって状態が変化しようがしまいがかまわない。