Greedy Algorithm: Light Bulbs (A Proof)

A pretty standard problem that anyone just starting out with practicing the greedy algorithm comes across is the light-bulb problem. While the solution to this problem is well-known, I haven’t yet found a good proof for its optimality.

Problem Statement

$N$ light bulbs are connected by a wire. Each bulb has a switch associated with it, however due to faulty wiring, a switch also changes the state of all the bulbs to the right of current bulb. Given an initial state of all bulbs, find the minimum number of switches you have to press to turn on all the bulbs. You can press the same switch multiple times.

Solution

The solution is quite easy to arrive at after you mess around with some smaller arrays. In short, we traverse the array from left to right, keeping track of whether we’re looking for a “0” bulb or a “1” bulb (since after flipping a switch, all “1” bulbs to the right become “0” bulbs and vice versa):

# A: List containing initial state of all bulbs
def bulbs(A):
    if sum(A) == len(A):
        return 0
    
    switch, flipped = 0, False
    for a in A:
        if not a and not flipped:
            flipped, switch = not flipped, switch + 1
        elif a and flipped:
            flipped, switch = not flipped, switch + 1
            
    return switch

Proof of Optimality

While I found good explanations for the solution on stackoverflow and others, I never was able to find a convincing argument as to why this greedy approach is the optimal one.

Let the array $A$ represent a binary number, i.e. if the array were $\left[ 1, 0, 1, 1\right]$ then it would correspond to the binary representation of $11$. Observe that performing a “switch” operation on a “0” bulb, i.e. switching on a bulb that is off, results in increasing the value of the number that $A$ represents. You can convice yourself of this mathematically and also look at some examples below:

int("10111", 2) # 23
int("11000", 2) # 24

# flipping the 2nd off bulb
int("101101101001", 2) # 2921
int("101110010110", 2) # 2966

Therefore, the greedy algorithm produces a set of monotonically increasing numbers that evetually terminate in $2^{N+1} - 1$. If any other algorithm were to not set the left-most $0$ to $1$ and instead choose some off-bulb which is further right, the sequence would not be monotonically increasing and would thus take more steps to reach termination. Therefore, the greedy algorithm gives the optimal solution.