Problem 8

There are $2026$ lightbulbs controlled by a number of switches, each switch controlling a subset of bulbs. Each bulb is controlled by at least one switch (perhaps more). When a switch is toggled, all bulbs controlled by that switch change state, i.e. turn on if they were off and turn off if there were on.

Suppose that all lightbulbs are off in the beginning, and we start toggling some switches to turn on as many lightbulbs as we can. What is the least number $n$ so that it is always possible to turn on at least $n$ lightbulbs at the same time, irrespective of the exact wiring of the switches?

To deter guessing without thinking, we ask that you also solve the following simple arithmetic problem before checking your answer:

If x = 5, y = 4 and z = 4, what is x + y - z?

This problem was first solved on Wed 11th March at 4:09:27pm