2. Given are $n$ light bulbs ($n>13$), each with its own switch. It is allowed to change the state of exactly 13 light bulbs simultaneously. Initially, some of the light bulbs are on, and some are off.

a) Is it possible to turn off all the light bulbs?

b) What is the minimum number of steps to turn off all the light bulbs if $n=111$ and all the light bulbs are initially on?
Solution. a) It can. If the number of lit bulbs at the beginning is greater than 13, then by turning off 13 bulbs each time, we can always reach a state where we have fewer than 13 lit bulbs. Clearly, in this case, it is sufficient to solve the problem assuming that $n=14$. Let's first assume that only one bulb is lit. Then we can proceed as shown in the table:

| lit | 1 | 12 | 3 | 10 | 5 | 8 | 7 | 6 | 9 | 4 | 11 | 2 | 13 | 0 |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| turned off | 13 | 2 | 11 | 4 | 9 | 6 | 7 | 8 | 5 | 10 | 3 | 12 | 1 | 14 |

Clearly, if the number of lit bulbs at the beginning was any other number between 2 and 12, we need to join the process described by the table at the appropriate point.

b) Since $8 \cdot 13 < 111$, we get that eight steps are not sufficient to turn off all the bulbs. We will prove that nine steps are sufficient. In the first seven steps, we turn off 13 bulbs each time, leaving 20 lit bulbs. In the eighth step, we turn off 10 and turn on 3 bulbs, and in the ninth step, we turn off the remaining 13 lit bulbs.