CMI-2018-DataScience-A: 20

Question

There are $7$ switches on a switchboard, some of which are $on$ and some of which are $off$. In one move, you pick any $2$ switches and toggle each of them—if the switch you pick is currently $off$, you turn it $on$, if it is $on$, you turn it $off$. Your aim is to execute a sequence of moves and turn all $7$ switches $on$. For which of the following initial configurations is this possible? Each configuration lists the initial positions of the $7$ switches in sequence, from switch $1$ to switch $7$.

• A. $\text{(off,on,on,on,on,off,on)}$
• B. $\text{(off,on,on,on,off,on,off)}$
• C. $\text{(off,on,off,off,on,off,on)}$
• D. $\text{(off,on,off,off,off,on,off)}$

Answer 1

$Ans) \ A, C$ 

Consider at the beginning we group the $on$ switches together and the $off$ switches together. (That is place the lights in two buckets ON and OFF)

When we toggle 2 switches,the following cases can occur:

1. We toggle an $on$ switch and an $off$ switch : Number of $on$ switches decreases by 1 due turning the switch off and increases by 1 when $off$ switch becomes on. Number of $off$ switches decreases by 1 and increases by 1 similarly. So net change is 0. (Even number of elements changed).
2. If the switches we select are both $on$, number of $on$ switches decreases by 2, number of $off$ switches increases by 2. Similarly is the case for selecting 2 $off$ switches. (Even number of elements changed)

So we see that number of $off$ switches changes by 2 or 0 in every move. So to turn every light on, we need to ensure that there are even number of $off$ switches, so that we can reduce it’s count by 2 in every move to make it 0.

Thus the valid cases have even number of $off$ switches.