3
$\begingroup$

You are in a room with six light switches. Down the hallway, there are two other rooms, each with three incandescent lightbulbs.

Each lightbulb is uniquely controlled by exactly one of the switches. At the start, all of the lightbulbs are switched off.

If you can only visit one of the two rooms at a time, what is the minimum number of visits required to be able to distinguish which switch corresponds to which bulb?

$\endgroup$
1
  • 2
    $\begingroup$ Given the classical nature of the puzzle, this extension has probably been asked before. I couldn't find a duplicate post but do let me know if you find one. $\endgroup$
    – mintmocha
    Commented Jul 31, 2023 at 7:44

2 Answers 2

5
$\begingroup$

With the allowed conditions light on/off-cold/off-warm, then the minimal number of visits is:

3

Strategy

For the first visit in a room 4 switches are turned on (s1-s4) and after some time 2 switches are turned off (s3-s4) before visiting a room. Two possible results: All three conditions are in the room (v1) or two different lightbulbs are in the same condition (v2)

For v1 the second visit is in the same room with s1, s3, s5 turned on. After this visit we know all three switches for this room and the remaining three switches for the second room. Two of this three switches are turned on and after some time one of the switches is turned off. With all different conditions on all three lightbulbs the puzzle is solved.

For v2 the second visit is in the same room. The two switches for the known two lightbulbs in the room are turned in the states on/off. The two switches for the last known lightbulb are also turned in different states on/off. After the visit we know all three switches for this room and the remaining three switches for the second room. Two of this three switches are turned on and after some time one of the switches is turned off. With all different conditions on all three lightbulbs the puzzle is solved.

$\endgroup$
1
$\begingroup$

If we are only allowed to look at the lights, then the minimal number of visits is:

5

Proof by code:

import collections
import itertools
 
matchings = [(p, (0,) * 6) for p in itertools.permutations(range(6))]
 
#by symmetry, on first pull we only care about number pulled
pull_sets0 = [(1,) * k + (0,) * (6 - k) for k in range(1,4)]
 
#only makes sense to pull 3 or fewer switches in 1 go
pull_sets = [x for x in itertools.product(range(2), repeat=6) if sum(x) <= 3]
 
def go(matchings, bound):
    if len(matchings) == 1:
        return 1
    if bound == 0:
        return 0
    for pull_set in (pull_sets0 if len(matchings) == 720 else pull_sets):
        new_matchings = []
        for m, s in matchings:
            s = list(s)
            for i, j in enumerate(m):
                if pull_set[i]:
                    s[j] ^= 1
            new_matchings.append((m, tuple(s)))
        match_groups_1 = collections.defaultdict(lambda: [])
        match_groups_2 = collections.defaultdict(lambda: [])
        for m, s in new_matchings:
            match_groups_1[s[:3]].append((m, s))
            match_groups_2[s[3:]].append((m, s))
        if len(matchings) == 720:
            match_groups_2 = {}
        for match_groups in (match_groups_1, match_groups_2):
            if len(match_groups) > 1:
                if all(go(ms, bound - 1) for ms in match_groups.values()):
                    return 1
    return 0
 
for bound in itertools.count(1):
    print(f"trying {bound}...")
    if go(matchings, bound):
        break
print("success!!")
$\endgroup$
3
  • $\begingroup$ I have a lower number in mind, but it depends on the type of light bulbs... $\endgroup$ Commented Jul 31, 2023 at 13:14
  • 1
    $\begingroup$ @sarsaparilla Are you referencing to the original question's answer which used a rot13(qvssrerapr orgjrra vapnaqrfprag naq YRQ yvtugohyof)? $\endgroup$ Commented Jul 31, 2023 at 17:12
  • $\begingroup$ @newQOpenWid I don't know the original question, but if we are using rot13(nyy vapnaqrfprag yvtug ohyof, jr pna yrirentr gur snpg gung gurl ner fgvyy ubg nsgre gurl unir orra ghearq bss. V pna vzntvar gung vs lbh pna grnpu lbhefrys ubj jnez n ohyo srryf n pregnva ahzore bs zvahgrf nsgre vg unf orra ghearq bss, gur chmmyr pbhyq or fbyirq jvgu bayl gjb ivfvgf.) $\endgroup$ Commented Aug 1, 2023 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.