5
$\begingroup$

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]

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Traklon Oct 31 '14 at 16:38
  • $\begingroup$ Must a sub board consist of consecutive rows and columns? $\endgroup$ – Calvin Lin Oct 31 '14 at 20:47
  • $\begingroup$ @CalvinLin Yes. $\endgroup$ – simmons Oct 31 '14 at 21:25
  • $\begingroup$ @Traklon You can improve that arrangement, by also flipping the bottom row (7 boards) and the right most row (7 boards). $\endgroup$ – Calvin Lin Nov 1 '14 at 16:11
  • $\begingroup$ @calvin That's what I was suggesteing, sorry for not being clear enough ! ^^ $\endgroup$ – Traklon Nov 1 '14 at 16:12
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.