Question 17
On the ceiling of a room hang 15 lamps, numbered from 1 to 15. Initially, all lamps are off. In another room there are 15 switches: a switch for lamps 1 and 2, a switch for lamps 2 and 3, a switch for lamps 3 and 4, and so on, up to a switch for lamps 15 and 1. When the switch for such a pair of lamps is flipped, each of those two lamps changes its state (from on to off or vice versa). The switches hang in a random order and all look identical. Raymond wants to find out which switch belongs to which pair of lamps. From the room with the switches he cannot see the lamps. He can, however, flip a number of switches and then walk to the other room to see which lamps are on. He can do this several times. What is the minimum number of times he must walk to the other room in order to know for certain, for each switch, which pair of lamps it belongs to?