解説
電球が ON
になるのは、状態が B
であるスイッチが奇数個あるときです。
答えは 2N−1 通りになります。
証明
スイッチが N=1 つのとき、 ON
になる組み合わせは 1 通りで、 2N−1 と表すことができます。
スイッチが N=k 個のときに ON
になる組み合わせが 2k−1 通りと仮定すると、スイッチを一つ追加したとき、新しいスイッチが A
のときに 2k−1 通り、 B
のときに 2k−1 通りで合計 2k 通りになります。 N=k+1 なので、 2k=2N−1 と表すことができます。
これで、 N≥1 となる全ての場合において電球が ON
となる組み合わせが 2N−1 通りであることが示されました。