We have 8 light switches in a room, each of which can be UP or DOWN. They all start DOWN. To do a complete test of the switches, we want to find a sequence of flipping one switch at a time so that, from each of the 28 possible positions of all the switches, we have flipped every switch at some point in the sequence, and so that we end with all switches DOWN. For example, if there are only 2 switches, from DD, we would need to test DD+DU and DD +UD from DU, we would need to test DU + DD and DU + UU from UD, we would need to test UD+ UU and UD + DD from UU, we would need to test UU + DU and UU+UD (Here is an example of a sequence of positions that tests all eight of the transitions above: (DD, DU, UU, DU, DD, UD, UU,UD, DD) (a) Use a counting argument to give a lower bound on the minimum length of the sequence of flips of 8 switches that meets the above condition. (b) Model this problem as a graph problem to give an argument as to how to achieve this lower bound. We have 8 light switches in a room, each of which can be UP or DOWN. They all start DOWN. To do a complete test of the switches, we want to find a sequence of flipping one switch at a time so that, from each of the 28 possible positions of all the switches, we have flipped every switch at some point in the sequence, and so that we end with all switches DOWN. For example, if there are only 2 switches, from DD, we would need to test DD+DU and DD +UD from DU, we would need to test DU + DD and DU + UU from UD, we would need to test UD+ UU and UD + DD from UU, we would need to test UU + DU and UU+UD (Here is an example of a sequence of positions that tests all eight of the transitions above: (DD, DU, UU, DU, DD, UD, UU,UD, DD) (a) Use a counting argument to give a lower bound on the minimum length of the sequence of flips of 8 switches that meets the above condition. (b) Model this problem as a graph problem to give an argument as to how to achieve this lower bound