Task 3. On the ceiling of a room, there are 15 lamps, numbered from 1 to 15. Initially, all the lamps are off. In another room, there are 15 switches: one switch for lamp 1 and 2, one switch for lamp 2 and 3, one switch for lamp 3 and 4, and so on, up to a switch for lamp 15 and 1. When the switch for such a pair of lamps is flipped, the status of each of those two lamps changes (from on to off or vice versa). The switches are arranged in a random order and all look identical. Raymond wants to find out which switch corresponds to which pair of lamps. From the room with the switches, he cannot see the lamps. However, he can flip a number of switches and then go to the other room to see which lamps are on. He can do this multiple times. How many times does he need to go to the other room at a minimum to be certain which switch corresponds to which pair of lamps?
Solution. With three rounds of walking, Raymond can never be certain. Indeed, if for each switch you note whether it is in the initial position or the flipped position in the three rounds, then you can get $2^{3}=8$ different patterns. However, there are 15 switches, so there are multiple switches with the same pattern, and Raymond can never distinguish these switches. Therefore, he must walk at least four times. We will prove that this is indeed sufficient.

Assume that Raymond, starting from the situation where all the lights are off, flips a number of switches. If he flips all the switches or none at all, then all the lights will still be off afterward. Otherwise, there will always be a light that has been changed by only one flipped switch, so it will be on. Consider such a light $i$ that is on. Then the switch with $i-1$ and $i$ or the switch with $i$ and $i+1$ has been flipped. (Consider the light numbers modulo 15.) First, assume that the latter is the case. Now consider light $i+1$. If it is off, then the switch with $i+1$ and $i+2$ has also been flipped; if it is on, then that switch has not been used. Next, we can deduce from the status of light $i+2$ whether the switch with $i+2$ and $i+3$ has been flipped or not. By continuing this process, we see that it is determined for all switches whether they have been flipped or not. In the second case, if it is precisely the switch with $i-1$ and $i$ that has been flipped, then it is also determined for all switches whether they have been flipped or not. Therefore, there are exactly two combinations of switches that result in the same status of the lights. If we choose one of these combinations and then flip all 15 switches again, the same lights will be on, so this must result in exactly the second combination of switches. If the first combination of switches contains an even number of switches, then the second combination contains 15 minus that number, so an odd number of switches.

However, Raymond knows himself how many switches he has flipped. He can deduce from the situation of the lights which two combinations of switches are possible, and only one of these can match the number of switches he has flipped. Therefore, he can precisely determine which lights the switches he has flipped correspond to; he only does not know which is which within that group of switches.

Now write the numbers 1 to 15 in binary notation. For this, a maximum of 4 digits are needed; pad with zeros if necessary so that each number is written with exactly 4 digits. Raymond numbers the switches with these binary numbers. In the first round, he flips the switches whose numbers in binary notation start with a 1 and notes the 8 corresponding light pairs. In the second round, he first resets all the switches and then chooses the numbers that have a 1 in the second position in binary notation. Similarly, in the third round, he chooses the third position in the binary notation, and in the fourth round, the fourth position. In each round, he can determine which light pairs the switches he has used correspond to (only not which is which). Since each switch corresponds to a unique combination of rounds, he can then figure out for each switch which light pair it controls. For example, if a certain light pair is turned on in the first round, not in the second round, in the third round, and also in the fourth round, then it corresponds to the switch with binary code 1011, which is switch 11. Therefore, he can succeed in four rounds of walking.