Least amount of trips

Question

There are two rooms. One room contains ten switches, and the other contains ten lights. Each switch controls one light, and no two switches control the same light. It is not known which switch controls which light, and it is your job to label them.

The problem is that, when you flip a switch, you can not immediately see which light has been turned on/off. You have to walk into the other room in order to find out.

What is the least amount of trips needed to label the switches?

We will call a trip any time that you leave the room with the switches.

We will say that you are in the room with the switches, and that all of the lights are on.

Bonus thoughts: what patterns emerge as you increase the amount of switches/lights?

Answer 1

Three switches version

A 3 switch version of this problem exits, which can solved in 1 trip taking into account the fact that light bulbs heat up when lit. The classical solution goes-

Turn on switches A, B and turn off B after (say) 5 minutes. Head over to the other room. The on light belongs to A, now, touch one of the bulb. It belongs to B if it is hot, else it belongs to C.

---

Non Heat Generating bulbs

In this case, we assume that the bulbs generate no heat. So, the heating trick cannot be used. Then, for $N$ bulbs the number of trips needed is: $$\lceil\log_2{N}\rceil$$

The strategy is -

Label each switch in binary. At the first trip, light the switches whose rightmost digit is 1. At the second trip light the switches whose second rightmost digit is 1 and so on...

This requires the number of digits in the binary representation of $N$, which equals $k=\lceil\log_2{N}\rceil$ trips. And the end of the trips, we can successfully determine each bit of the binary representation of each bulb (0 if off, 1 if on) and hence identify their switches.

For $N=10$ the answer is $\lceil\log_2{10}\rceil = 4$

Heat Generating Bulbs

This is similar to the previous case, but now we have $3$ possible states of the bulb ON, OFF, HOT. In this case we simply use base 3 numbers to label each switch and identify each trinary digit and hence the answer is: $$\lceil\log_3{N}\rceil$$ For $N=10$ the answer is $\lceil\log_3{10}\rceil = 3$

Multiple states of hot

Now suppose, we can have two kinds of hot- warm and very hot. then we have 4 states and we work in base 4. In general if there are $k-2$ states of hot, the answer is: $$\lceil\log_k{N}\rceil$$

Extreme Solution

Suppose we have extremely accurate thermometer. Then we can label the bulbs in one trip!

Light up each bulb one after one at one minutes interval. Head to the other room, measure the temperatures, The highest belongs to the first lit switch, the second highest to the second lit and so on..

This is equivalent to working in base $N$.

Answer 2

If we assume that

the lights cannot be touched so that the trick from the 3 lights version (1 light off and cold, 1 light off and warm, 1 light on) doesn't work

then

using $N$ trips you can distinguish $2^N$ lights, meaning that $4$ trips are needed for $10$ lights.

Usage scheme:

Assign a number to each switch, starting with 0. Convert each number to base 2 (i.e. binary). For 0 to 9 we get:

0: 0000
1: 0001
2: 0010
3: 0011
4: 0100
5: 0101
6: 0110
7: 0111
8: 1000
9: 1001

During the first trip turn off switches with 0 in the first column, turn on the ones with 1. Use the other columns for the next trips. For each light assign 0 for each trip if it's off, and a 1 otherwise. Match the number of the light to the number of the switch, after all trips are done.

If we assume

that we can differentiate more than 2 states by varying the duration of the lights turned on and measuring the temperature of the lights, and we call the number of states $S$

then

using $N$ trips we can distinguish $S^N$ lights. The usage scheme is similar to the one above, but we need to convert each number to base $S$.

Answer 3

If you don't want to do any damage, it will take:

3 Trips

For each trip you can determine if the bulbs are in one of 3 states

Either the bulb is on, it is off and cold, or it is off and still warm.

The technique for 10 bulbs is:

1. Switch off all bulbs and let them cool down.
2. Switch on 6 (say switches A-F) and after 10 minutes switch half of them off (D, E and F).
3. Go to the other room and test to see if the lights are on, off or warm.
4. Repeat as above, but this time set switches A, D and G to ON, B, E and H to WARM and leave the others off.
A: ON ON
B: ON WARM
C: ON COLD
D: WARM ON
E: WARM WARM
F: WARM COLD
G: COLD ON
H: COLD WARM
I: COLD COLD
J: COLD COLD
This will allow you to tie every light to every switch except for I and J which have both been off the entire time. Switch one of these on for the final test and all the bulbs will have been identified.

For the general case where there are $N$ lightbulbs

the number of trips is given by rounding $log3(N)$ up to the next whole number.

We can improve on the case for 10 lightbulbs:

If, while we are initially waiting for all the bulbs to cool down, we repeatedly switch J on and off so that the filament blows, then proceed as above, then on the first trip to the room one bulb would be blown (visible on close inspection of one of the off bulbs), leaving only nine to discriminate between which can be handled with one more trip.