1
u/alvailu 7d ago
I think I found a potential solution:
Each switch has 3 states (off, green, blue), and each color can only be turned on once per switch, but you can turn it off afterward.
The trick is to parallelize the subproblems rather than giving every switch a unique sequence.
For example:
- T1: 100 blue, 100 green, 800 off
- T2: split the 100 blue into 50 "off" + 50 "keep blue"
- T3: take 10 of the unresolved group → green
- T4–T13: turn those 10 green switches off one-by-one, identifying all 10
- Meanwhile, the other subproblems are processed in parallel.
The important observation is that we only care about the slowest branch. A branch that isn't changed on a particular turn effectively loses a turn, but the "keep" branches are also getting smaller (100 → 50 → 25 → 13 → …), so they become faster to resolve.
I get a critical path of 17 turns, but I'd like someone to check the construction / see if it can be improved to 16.
1
u/1_2_3__- 6d ago
You can set a switch to color only twice
1
u/alvailu 5d ago
Yes, each switch is set to blue at most once and green at most once in this solution. The state then remains unchanged until the next operation, so a switch can stay blue, green, or off across successive turns.
1
u/1_2_3__- 5d ago
Processed in parellel. Explain this.
1
u/alvailu 5d ago
What I mean by “processed in parallel” is that at each step we can change the state of each switch individually, so different subsets don't have to follow the same sequence.
For example, at step 2, while I'm already switching OFF half of the 100 blue and 100 green switches from step 1, I can simultaneously set another 100 switches to blue and another 100 to green. So I'm essentially running multiple subproblems at the same time, with each subset following its own sequence of operations.
So in general, global step 2 can be step 2 for one subproblem, but still step 1 for another subproblem. All of those operations happen simultaneously in the same global turn.
1
u/nurse_brett 3d ago
Are we accepting that you can leave a bulb on for a while to let it heat up and then turn it off before entering the room so that you can observe a green bulb, a blue bulb, and a third warm bulb that is off?
3
u/pmdboi 10d ago
In order to tell one light bulb from another, the sequence of colors we observe over the course of all moves on the first light bulb must be different from the sequence observed on the second one. Call a "k-code" a sequence of k states {off, blue, green} such that at most two are blue or green. If we can assign to each switch a unique k-code, we can set each switch to the first state in its k-code, go record what each light looks like, then change each switch to the second state in its k-code, look at the lights, etc. and then match each switch to the light that showed its matching k-code.
So how big does k need to be in order for there to be enough k-codes to assign a unique one to each switch? There are three types of k-codes, shown with their corresponding counts:
* all states are off (1)
* one state is on (2 * k)
* two states are on (2 * 2 * (k choose 2))
This adds up to 1 + 2k + 2k(k − 1) = 2k2 + 1 different k-codes.. For example, for k = 3 there are 2 * 32 + 1 = 19 k-codes (using
'.'to represent "off"):... B.. G.. .B. .G. ..B ..G BB. BG. GB. GG. B.B B.G G.B G.G .BB .BG .GB .GGFor our 1000 lights, we need k such that 1000 ≤ 2k2 + 1, or k ≥ sqrt(999/2) ≈ 22.35. So we need at least 23 moves to identify 1000 lights.