Learn / Library / Brainteasers
All lamps on a grid
A by grid of lamps starts with every lamp on. Pressing a lamp toggles it and the lamps that share an edge with it (on becomes off and off becomes on). What is the minimum number of presses that turns all lamps off?
Checking an answer needs JavaScript. The hint and the solution open without it.
Hint
A single press toggles at most lamps. Is that enough to give a lower bound and then a matching plan?
Solution
- A press toggles at most lamps, and presses toggle at most lamps in total, which is fewer than the lamps that must change, so at least presses are needed.
- Number rows and columns from to . Pressing the lamps , , and , which each lie on the border and so toggle exactly lamps, toggles lamps in total.
- These presses toggle the lamps , , , ; , , , ; , , , ; , , , , which are all different, so every lamp is toggled once.
- The minimum number of presses is .
Answer: