Minimum number of bad lamps on a board
Source: MEMO 2017 T3
August 25, 2017
combinatorics
Problem Statement
There is a lamp on each cell of a board. Each lamp is either on or off. A lamp is called bad if it has an even number of neighbours that are on. What is the smallest possible number of bad lamps on such a board?
(Two lamps are neighbours if their respective cells share a side.)