Problem 31. Lights
The school wherein Roshank studies has 10 lamps at the highest point of the ceiling. Each of these lamps is controlled by a separate key in the control room in the basement. There are 10 keys in the control room but Roshanak doesn’t know which key controls which light.
Roshank is very tired and does not want to go to the control room more than 3 times. How many key-light pairs can she figure out with going to the basement three times? Each time she goes to the control room, she can turn some of the keys on and off and then come back and see which lights are on. All the lights are off in the beginning.
Link to the problem on Twitter: https://twitter.com/Riazi_Cafe/status/1698250117898486041
The answer is 7.
For each key, let us denote the off position by 0 and the on position by 1. Thus, if we combine the three positions of a key in the three visits of Roshanak to the control room, there are 8 possibilities for each key: 000,001,010,011,100,101,110,111. We denote this string of length 3 by the configuration of a key.
Suppose we have only one key that follows the pattern 001. That is, in the first visit it is set to off, in the second visit, it is set to off, and in the third visit it is set to on. In this case, there will be only one light bulb that follows this on/off pattern and we can find out the pairing. More precisely, we can detect a key-light pairing if and only if the corresponding key has a unique configuration.
Since the number of unique configurations is 8, the high number of keys with unique configurations is 7. More precisely, we can give a unique configuration to the first 7 keys and use the last configuration for the remaining 3 keys.