There is a lamp on each cell of a board. Each lamp is either on or off. A lamp is called [i]bad[/i] 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.)
Problem 1280
Official solution
1. Claim: The minimum number of bad lamps on a board is 1. This is true for any board when is odd.
2. Proof:
- Existence of a configuration with 1 bad lamp:
- Consider placing a bad lamp in the center of the board and working outward in rings. This configuration ensures that only the center lamp is bad, and all other lamps have an odd number of neighbors that are on. This is a non-trivial configuration but can be constructed.
- Non-existence of a configuration with 0 bad lamps:
- Assume there exists a configuration with 0 bad lamps.
- Using chess notation, consider the cells , , and :
- If both and are off, is bad.
- If both and are on, is bad.
- Therefore, exactly one of and must be on.
- Similarly, consider the cells , , and :
- If both and are off, is bad.
- If both and are on, is bad.
- Therefore, exactly one of and must be on.
- Continue this process along the diagonal to the center of the board. After 1008 steps, we find that the cells left and below the center cell must both be on or both be off to avoid making the cell diagonally to the left bottom of the center cell bad.
- By symmetry, starting from the other three corners along their respective diagonals, we find that all four cells neighboring the center must be of the same parity (either all on or all off).
- However, this makes the center cell bad, as it will have an even number of neighbors that are on.
- This contradicts the assumption that there are 0 bad lamps.
3. Conclusion:
- Therefore, the smallest possible number of bad lamps on a board is 1.
The final answer is