You have a system of n switches, each of which can be in one of two states: off or on. There

are 2n possible configurations of this system. For example, when n = 2 the four possible

configurations for the pair of switches are (off, off), (off, on), (on, off), and (on, on).

6. You have a system of n switches, each of which can be in one of two states: OFF or ON. There are 2" possible congurations of this system. For example, when n = 2 the four possible congurations for the pair of switches are (OFF, OFF), (OFF, ON), (ON, OFF), and (ON, ON). Initially, all switches are OFF. In each step, you are allowed to ip exactly one of the switches. Is there a sequence of ips that makes each possible conguration arise exactly once? For example when n = 2 this sequence of ips has the desired property (the number on the arrow indicates the switch that is ipped): (OFF, OFF) i> (OFF, ON) i> (ON, ON) i> (ON, OFF) (a) Show a sequence of ips that works when n = 3. (b) Prove that for every n 2 1, there exists a sequence of ips for n switches that covers every possible conguration exactly once, starting with the all OFF conguration. (Hint: Use induction. You may need to strengthen the proposition.) (c) Now suppose that you ip not one but two switches at a time. Prove that for every n 2 2, there is no sequence of ips for n switches that covers every possible conguration exactly once, starting with the all OFF conguration. (Hint: Use an invariant.) (d) (Extra credit) If you ip three switches at a time, for which values of n can the task be accomplished