Problem 889

Solution. Number the rows from 1 to 2014 and the columns as well. Consider the following initial situation: in row $i$, the lamps in columns $i, i+1, \ldots, i+1005$ are on and the rest are off, where we calculate the column numbers modulo 2014. Now, in each row and each column, exactly 1006 lamps are on. Therefore, no move is possible. It is thus not always possible to reach a situation with fewer than $2014 \cdot 1006$ lamps on.

Now, let's show that we can always reach a situation with at most $2014 \cdot 1006$ lamps on. Suppose, for the sake of contradiction, that in a certain situation there are at least $2014 \cdot 1006 + 1$ lamps on and it is not possible to reduce the number of lamps on. If there is a row or column with 1008 or more lamps on, we can change the status of the lamps in this row or column, and there will be fewer lamps on afterward, a contradiction. Therefore, in every row and column, there are at most 1007 lamps on.

Let $I$ be the set of rows with exactly 1007 lamps on, and let $J_{1}$ be the set of columns with exactly 1007 lamps on. We plan to change the status of the lamps in all rows in $I$. This is called the big plan. If after executing the big plan, a column has 1008 or more lamps on, we get a contradiction again, so we assume that this does not happen. Let $J_{2}$ be the set of columns that will have exactly 1007 lamps on after executing the big plan. If there is a cell $(i, j)$ with $i \in I$ and $j \in J_{1}$ where the lamp is off, I can change row $i$ and get more than 1007 lamps on in column $j$, a contradiction. Therefore, every lamp at $(i, j)$ with $i \in I$ and $j \in J_{1}$ is on. If there is a cell $(i, j)$ with $i \in I$ and $j \in J_{2}$ where the lamp is off after executing the big plan, I get a contradiction in the same way. Therefore, every lamp at $(i, j)$ with $i \in I$ and $j \in J_{2}$ is on after executing the big plan. Since the columns in $J_{2}$ each have exactly 1007 lamps on after executing the big plan, they had $1007 - |I|$ lamps on before the big plan. (The notation $|X|$ denotes the number of elements in the set $X$.) The columns in $J_{1}$ each have exactly 1007 lamps on, and this also means that $J_{1}$ and $J_{2}$ are disjoint (no overlapping columns). The remaining columns have at most 1006 lamps on. The total number of lamps on before the big plan is thus at most

$$(1007 - |I|) |J_{2}| + 1007 |J_{1}| + 1006 (2014 - |J_{1}| - |J_{2}|) = 1006 \cdot 2014 + |J_{1}| + |J_{2}| - |I| \cdot |J_{2}|$$

This must be at least $1006 \cdot 2014 + 1$, so $|J_{1}| + |J_{2}| - |I| \cdot |J_{2}| \geq 1$. This implies $|J_{1}| > (|I| - 1) |J_{2}|$. If $|I| \geq 2$, then $|J_{1}| > |J_{2}|$. By executing the big plan, the number of columns with 1007 lamps on is thus reduced. But then we have a situation again with $|I|$ rows with 1007 lamps on, where $J_{1}$ and $J_{2}$ are exactly swapped. So we can execute a new big plan, which again reduces the number of columns with 1007 lamps on. Contradiction, because we are back in the initial situation. We conclude that $|I| = 1$ must hold.

We thus have the situation that there is exactly one row with exactly 1007 lamps on. Similarly, we can show that there must also be exactly one column with exactly 1007 lamps on. Since there are $1006 \cdot 2014 + 1$ lamps on, there must be exactly 1006 lamps on in every other row and column. Now change the status of the lamps in the row with 1007 lamps on. In 1007 columns, there will then be $1006 + 1 = 1007$ lamps on. We have already seen that in this situation, the number of lamps that are on can be reduced.

We see that if there are more than $1006 \cdot 2014$ lamps on, it is always possible to reduce this number. Therefore, the smallest $k$ is $1006 \cdot 2014$.