There is a lamp on each cell of a $2017 \times 2017$ 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.)
Problem
Source: MEMO 2017 T3
Tags: combinatorics
01.09.2017 09:31
Claim: The minimum of bad lamps on a $2017\times 2017$ board is 1 (This is true on any $n\times n$ board when $n$ is odd, by the way). Proof: I) A constellation with 1 bad lamp exists. Perhaps somebody can link a picture, I am not sure if I am allowed to - as a relatively new user. Hint: Start with a bad lamp in the center and work in rings outward. There are a lot of different minimal constellations - not trivial to find, though. II) Lets assume a constellation with $0$ bad lamps exists. Lets look at some necessary conditions... Using chess notation for the cells, exactly one of the lamps on $a2$ and $b1$ must be turned on (otherwise $a1$ is bad). Exactly 0 or 2 lamps of $b3$, $c2$ must be turned on (otherwise $b2$ is bad). Exactly one of the lamps on $c4$ and $d3$ must be turned on (otherwise $c3$ is bad). In this manner we continue along the diagonal (in exactly 1008 steps) to the center and find: the cells left and below the center cell are both on or both off (otherwise the cell diagonally to the left bottom of the center cell is bad). As we can start from the other three corners along their respective diagonal we find that all the four cells neighboring the center are necessarily of the same parity (i.e., on/off). But then the center is bad. Contradiction to 0 bad lamps.
02.09.2017 10:15
My proof from above can be simplified: It is sufficient to consider the 2017 cells of one single diagonal. As described above, start with $a1, b2, c3, \ldots$ but continue the whole diagonal to the opposite corner. If we start with $a1, b2, \ldots $ all being good lamps, then the opposite corner is necessarily a bad lamp (since 2017 is odd). It is not possible that all diagonal cells are good cells! Thus we have additionally proven that for ALL minimal solutions the center cell contains the single bad lamp (since both diagonals must contain at least one bad lamp).
14.01.2019 16:36
Here is a picture which shows construction for any $(4k+1)\times (4k+1)$. [asy][asy] path rect(int i, int j) { return (i,j)--(i,j+1)--(i+1,j+1)--(i+1,j)--cycle; } fill(rect(6,6),red); fill(rect(5,4),red); fill(rect(4,4),red); fill(rect(4,7),red); fill(rect(4,8),red); fill(rect(7,8),red); fill(rect(8,8),red); fill(rect(8,4),red); fill(rect(8,5),red); fill(rect(2,5),red); fill(rect(2,6),red); fill(rect(5,10),red); fill(rect(6,10),red); fill(rect(10,6),red); fill(rect(10,7),red); fill(rect(6,2),red); fill(rect(7,2),red); fill(rect(2,2),red); fill(rect(3,2),red); fill(rect(10,2),red); fill(rect(10,3),red); fill(rect(2,9),red); fill(rect(2,10),red); fill(rect(9,10),red); fill(rect(10,10),red); fill(rect(0,0),red); fill(rect(1,0),red); fill(rect(4,0),red); fill(rect(5,0),red); fill(rect(8,0),red); fill(rect(9,0),red); fill(rect(12,0),red); fill(rect(12,1),red); fill(rect(12,4),red); fill(rect(12,5),red); fill(rect(12,8),red); fill(rect(12,9),red); fill(rect(0,3),red); fill(rect(0,4),red); fill(rect(0,7),red); fill(rect(0,8),red); fill(rect(0,11),red); fill(rect(0,12),red); fill(rect(3,12),red); fill(rect(4,12),red); fill(rect(7,12),red); fill(rect(8,12),red); fill(rect(11,12),red); fill(rect(12,12),red); for(int i=0; i<14; ++i) { draw((i,0)--(i,13)); draw((0,i)--(13,i)); } [/asy][/asy]
14.01.2022 15:22
MarkBcc168 Very nice solution