Some Christmas lights are arranged using magical wires. Each light can be green or yellow. Each wire is connected to two lights and has a magical property: when someone touches a wire connecting two lights, each of them changes color from green to yellow or from yellow to green.

a) In the arrangement below, each point represents a light and the segments represent the magical wires. At the beginning, all of them are yellow. What is the minimum number of wires we need to touch so that all the lights turn green? Show an example of how to make this change with the minimum number of wires.

![](https://cdn.mathpix.com/cropped/2024_05_01_360f8ce7ec440aed2c7ag-24.jpg?height=320&width=463&top_left_y=859&top_left_x=702)

b) Consider the arrangement in the following figure where all the lights are yellow. Show that it is not possible to touch some magical wires and change the color of all the lights to green.

![](https://cdn.mathpix.com/cropped/2024_05_01_360f8ce7ec440aed2c7ag-24.jpg?height=323&width=685&top_left_y=1426&top_left_x=594)
Solution

a) Each wire we touch changes the color of exactly two lamps. Since there are 16 yellow lamps, we must touch at least 8 wires. The figure below shows an example of wire choices that make this possible:

![](https://cdn.mathpix.com/cropped/2024_05_01_360f8ce7ec440aed2c7ag-24.jpg?height=340&width=471&top_left_y=2286&top_left_x=701)
b) Note that the configuration given in part b) has exactly 23 lamps. Observe that when we touch a magic wire, there are three possible changes in the lamps:

i) Two green lamps can turn into two yellow lamps.

ii) Two yellow lamps can turn into two green lamps.

iii) One green and one yellow lamp can turn into one yellow and one green lamp.

Thus, the number of green lamps either decreases by 2, increases by 2, or remains the same. Therefore, if we start with 0 green lamps, we will always have an even number of green lamps. Since 23 is odd, it is not possible to turn all 23 lamps green.