There are $15$ lights on the ceiling of a room, numbered from $1$ to $15$. All lights are turned off. In another room, there are $15$ switches: a switch for lights $1$ and $2$, a switch for lights $2$ and $3$, a switch for lights $3$ en $4$, etcetera, including a sqitch for lights $15$ and $1$. When the switch for such a pair of lights is turned, both of the lights change their state (from on to off, or vice versa). The switches are put in a random order and all look identical. Raymond wants to find out which switch belongs which pair of lights. From the room with the switches, he cannot see the lights. He can, however, flip a number of switches, and then go to the other room to see which lights are turned on. He can do this multiple times. What is the minimum number of visits to the other room that he has to take to determine for each switch with certainty which pair of lights it corresponds to?
Problem
Source: 2022 Dutch IMO TST 2.3
Tags: combinatorics
27.10.2024 01:22
The answer is 4. The main claim is that if I know how many light switches I've flicked and what lights are on I can determine the set of the light switches I turned on. there are $2^15$ choices of which lights will be on, and clearly the possible options with these light switches are only when there is an even amount of lights on, so there are $2^14$ actual possible configurations. I have $2^15$ options for what light switches to flick, and I know I can pair them up to get the same configuration (flicking the opposite set of light switches leaves the lights the same). Since 15 is odd, if I know the configuration of lights I can tell what the 2 options for sets of light switches are, and by knowing how many light switches I flicked I know exactly which set it was. Now we only need an information argument: If I use at most 3 visits, I'll have some 2 switches in the same state in all 3 visits so I can't tell them apart. With 4 visits I can flick the switches in the i-th visit by their i-th bit, and then I can tell any 2 apart, so I know precisely which switch corresponds to which lights.