# Maximum number of squares with same number

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]

• We can do better by adding a last subboard at the end. It will create $2$'s and $3$'s, but we will add more $1$'s than we will lose. – Traklon Oct 31 '14 at 16:38
• Must a sub board consist of consecutive rows and columns? – Calvin Lin Oct 31 '14 at 20:47
• @CalvinLin Yes. – simmons Oct 31 '14 at 21:25
• @Traklon You can improve that arrangement, by also flipping the bottom row (7 boards) and the right most row (7 boards). – Calvin Lin Nov 1 '14 at 16:11
• @calvin That's what I was suggesteing, sorry for not being clear enough ! ^^ – Traklon Nov 1 '14 at 16:12

[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.$