Problem 2025

Solution:

We divide the square in $1 \times 1$-squares and color the square in checkerboard fashion such that the corners are black and we call lamps on black and white squares black and white lamps, respectively. We assign the number 1 to a lamp that is on, and the number 0 to a lamp that is off.

If we assign coordinates $(0,0)$ to the lamp in the center, we see that the black lamps are exactly the lamps with the coordinates $(i, j)$ where $i+j$ is even.

Now we assume that the minimum number is 0, that is, there is a configuration where every lamp has an odd number of neighbours that are on, and we try to get a contradiction. For every black lamp with coordinates $(i, j), i$ and $j$ even, we add the numbers associated to its neighbours, and add all these numbers. The parity of this sum $S$ can be determined in the following two ways:

On the one hand, we know that every lamp has an odd number of neighbours with value 1, so we simply have to determine the number modulo 2 of lamps with $i$ and $j$ even. Since we can group lamps at $(i, j)$ with lamps at $(-i,-j)$ and the lamp in the center is the only one left, we get that $S$ is odd.

On the other hand, every white lamp enters the sum as often as it has neighbours with $i$ and $j$ even. But there are exactly two such lamps because exactly one of the coordinates of the white lamp is odd and can be modified with plus or minus 1 to get a neighbour with two even coordinates. There are no problems at the boundary because this process will not change the coordinate $\pm 1008$ so we will stay inside the square. Therefore, $S$ is even, which is clearly a contradiction.

So, it is impossible that all lamps have an odd number of neighbours that are on.

Now, we will provide a concrete arrangement where all lamps except for the lamp at the center have an odd number of neighbours that are on.

For the black lamps, i.e. $i+j$ even, we choose the values:
$$f(i, j)= \begin{cases}0, \text{ if } \max (|i|,|j|) \equiv 0,1 \bmod 4 \\ 1, \text{ if } \max (|i|,|j|) \equiv 2,3 \bmod 4\end{cases}$$
For the white lamps, i.e. $i+j$ odd, we choose the values:
$$f(i, j)= \begin{cases}0, \text{ if } \max (|i|,|j|-1) \equiv 0,1 \bmod 4 \\ 1, \text{ if } \max (|i|,|j|-1) \equiv 2,3 \bmod 4\end{cases}$$
(This assignment can be found by replacing 2017 with a small number, say 17, starting with a row of zeros, using the assumptions to determine the rest and then notice that the zeros and ones for black or white lamps only form frames of depth 2 around the center.)

It is now easily checked that the condition is satisfied for all non-central lamps:

For a white lamp we assume without loss of generality $|i|<|j|$ (equality is impossible because they have different parity). Then, for the neighbours $(i \pm 1, j)$ and $(i, j \pm 1)$, the bigger coordinates are $|j-1|,|j|,|j|$ and $|j+1|$ and we can check easily that an odd number of them are $\equiv 2,3 \bmod 4$.

For a black lamp with $j>0$ or $j<0$, we argue analogously. If $j=0$, then $i \neq 0$ for a non-central lamp, therefore the maximum is $|i|$ and we have again the values $|i-1|,|i|,|i|$, $|i+1|$ to check which contain an odd number of values $\equiv 0,1 \bmod 4$.

Therefore, we have found an arrangement with exactly one lamp with an even number of neighbours that are on as desired.

The images show the discussed optimal arrangement for $n=77$. Lamps that are on are yellow, lamps that are off are blue. The first image shows all lamps, the second image shows the lamps with $i+j$ even and the third image shows the lamps with $i+k$ odd.

Solution:

We color the board as a chess board in such a way that the four corners are white.

An active lamp on a black field has no influence on the number of active neighbours of any lamp on a black field, and vice versa an active lamp on a white field has no influence on the number of active neighbours of a lamp on a white field. Therefore, we can optimize the number of lamps with an even number of active neighbours separately for lamps on black and white fields.

For the black fields, it is easy to find an arrangement in which all black fields have exactly one active neighbour, by turning on the following lamps: In the 1st, 5th, 9th, 13th, $\ldots$ row the 1st, 5th, 9th, 13th, ... lamp (so all lamps with $x \equiv y \equiv 1 \bmod 4$, assuming that the corner has coordinates $(1,1)$), and in the 3rd, 7th, 11th, ... row the 3rd, 7th, 11th, ... lamp (so all lamps with $x \equiv y \equiv 3 \bmod 4$).

An example for $n=77$ with the same color coding as in the previous solution:

For white fields, we first show that at least one white field has to have an even number of active neighbours. To do so, we colour all white fields in the 1st, 3rd, 5th, ... row and in the 1st, 3rd, 5th, ... column red. Each black field is neighbour to exactly two red fields, and red fields have only black neighbours. If $x$ lamps on black fields are active, then all red fields together have exactly $2x$ active neighbours. Since the number of red fields is odd, at least one of them has to have an even number of active neighbours.

All that is left to do is finding an arrangement in which all white fields except for one have an odd number of active neighbours. To do so, we separate the board into four "triangles" roughly as follows:

In the upper triangle we turn on the following lamps: In the 1st, 3rd, 5th, ... row always the lamp on the second field from the left, and then every 4th lamp, like this:

For filling the other triangles, we rotate the same pattern by $90^\circ$. Each lamp is only neighboured to fields from the own triangle, and each field within the triangle has exactly one active neighbour. Only the field in the middle of the board is left.

An example for $n=77$:

Altogether, the pattern looks like this: