Maths Olympiad Prep

Track / Stage 6 / 280 of 400 #1280 of 1964

Problem 1280

National olympiad, first round
Combinatorics Difficulty 6.5 Find the answer

There is a lamp on each cell of a 2017×20172017 \times 2017 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.)

A number or a short expression. Spacing and $ signs are ignored.

Official solution

1. Claim: The minimum number of bad lamps on a 2017×20172017 \times 2017 board is 1. This is true for any n×nn \times n board when nn 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 a1a1, a2a2, and b1b1:
- If both a2a2 and b1b1 are off, a1a1 is bad.
- If both a2a2 and b1b1 are on, a1a1 is bad.
- Therefore, exactly one of a2a2 and b1b1 must be on.
- Similarly, consider the cells b2b2, b3b3, and c2c2:
- If both b3b3 and c2c2 are off, b2b2 is bad.
- If both b3b3 and c2c2 are on, b2b2 is bad.
- Therefore, exactly one of b3b3 and c2c2 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 2017×20172017 \times 2017 board is 1.

The final answer is 1\boxed{1}

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.