解説

電球が ON になるのは、状態が B であるスイッチが奇数個あるときです。

答えは 2N12^{N-1} 通りになります。

証明

スイッチが N=1N=1 つのとき、 ON になる組み合わせは 11 通りで、 2N12^{N-1} と表すことができます。

スイッチが N=kN=k 個のときに ON になる組み合わせが 2k12^{k-1} 通りと仮定すると、スイッチを一つ追加したとき、新しいスイッチが A のときに 2k12^{k-1} 通り、 B のときに 2k12^{k-1} 通りで合計 2k2^k 通りになります。 N=k+1N=k+1 なので、 2k=2N12^k=2^{N-1} と表すことができます。

これで、 N1N \ge 1 となる全ての場合において電球が ON となる組み合わせが 2N12^{N-1} 通りであることが示されました。