Given a $1000\times 1000$ board. At the beginning, all cells have $0$ written on it. In an operation, we are allowed to choose any $130\times 130$ subboard and increase every number in this subboard by $1$. We can perform this operation as many times as we like. What is the maximum number of cells with the same (non-zero) number?
We can choose non-overlapping $130\times 130$ subboards to cover a $910\times 910$ subboard, yielding $910^2$ squares with the same number, $1$. Is this optimal, or can we do better?
[Source: Based on Russian competition problem]
[This is not a solution.]
Let the cells be $(i,j)$, where each ordinate runs from 1 to 1000. $(1,1)$ is in the top left corner.
We define each 130 by 130 sub board by its top left cell. We have $(1000-130+1)^2 $ boards of the boards, defined by $ ( i, j)$, where each ordinate runs from 1 to 871.
We flip the following boards:
49 boards of the form $ ( 130 i + 1, 130 j + 1)$,
7 boards of the form $ ( 871, 130j + 1)$,
7 boards of the form $(130i+1, 871)$,
1 board of the form $(871, 871)$.
Then, most of the cells are 1, except those of the form
1) $ (i, j)$ where $ 871 \leq i \leq 910$ and $j$ is anything.
2) $(i,j)$ where $i$ is anything and $ 871 \leq i \leq 910$.
This gives us equal cells for $ 1000^2 - 40 \times 1000 - 40 \times 1000 + 40^2 = 921600.$