, 2015

For a pair of integers $u, v$ and a positive integer $m$ we write $u \equiv v \pmod m$ to mean that $u - v$ is divisible by $m$.

Let us call an $a \times a$ square box of the given grid a region. When $n \ge a$, if we color black all of $n \times 1$ square boxes stacked consecutively on a vertical strip, the rectangular patch of the grid consisting of $n \times (2a-1)$ squares formed by the $n$ black $1 \times 1$ vertically stacked boxes and their $2a-2$ horizontal translates ($(1, 2, \dots, a-1)$ to the left and $(1, 2, \dots, a-1)$ to the right) has the property that any region contained in the interior of the patch satisfies the requirement of the problem. So, we see that $K = a(n+1-a)$ is satisfied.

Next, we show that for all sufficiently large $n$, we get $K \le a(n+1-a)$. For a region $R$, having $x$ black $1 \times 1$ squares, define
$$\mathcal{L}(R) = \begin{cases} x, & \text{if } x \le a-1, \\ x-a, & \text{if } x \ge a. \end{cases}$$
and call it a loss for $R$. There are $a^2 n$ pairings of a black square and a region containing it. Let $L = \sum \mathcal{L}(R)$, where the sum is taken over all regions containing black boxes. For $K$ regions $R$ that satisfy the requirement of the problem $\mathcal{L}(R) = 0$, while other regions $R'$ appearing as a summand for the definition of $L$ above, contain more black squares than $\mathcal{L}(R')$, we have $aK \le a^2 n - L$. So, it is sufficient to show that there exists an $N$ such that if $n \ge N$, then $L \ge a^2(a-1)$.

So, let $N = (a^2(a-1) - a)^2 + 1$. We will show that if $n \ge N$, then $L \ge a^2(a-1)$ holds. In the sequel, let us call contiguous $a$ rows of squares in the grid a horizontal line and contiguous $a$ columns of squares in the grid a vertical line. Then we see that either $a^2(a-1)$ or more horizontal lines or $a^2(a-1)$ or more vertical lines will contain at least one black square. Therefore, if we assume that $L < a^2(a-1)$ holds, then at least one of the horizontal lines in the former case, or at least one vertical in the latter case must have the property that $\mathcal{L}(R) = 0$ must hold for any region $R$ contained in it. (Note that by definition $\mathcal{L}(R) = 0$ if the region $R$ does not contain any black square.) By symmetry, we may and do assume that such a horizontal line exists. Take one such horizontal line and call the lowest row the 0-th row and the row $y$ steps above the 0-th row the $y$-th row, where $y$ is a positive integer. Let $A$ be a black box in this horizontal line lying on the left-most position. Among the regions contained in this horizontal line, those containing $A$ in the rightmost column must contain $a$ black squares, we see that every square in the column where $A$ is located must be black-colored. Furthermore, among regions contained in this horizontal line and containing $A$ in their left-most column, all the $a-1$ columns lying to the right of the column containing $A$ do not contain any black squares, since the column containing $A$ has a black square. (Since $A$ is the black square having the left-most position in the horizontal line, all of the $a-1$ columns lying to the left of the column containing $A$ contain no black squares either.)

Let us next show that for any vertical line containing $A$, the sum of the $\mathcal{L}(R)$ for all the regions $R$ contained inside of the vertical line is at least $a(a-1)$. Fix one such vertical line, and let $R_y$ be a region contained in the vertical line and its lowermost row is the $y$-th row. Let $f(y) = \mathcal{L}(R_y)$ and denote by $g(y)$ the number of black squares contained in $R_y$. Then we have $f(y) \equiv g(y) \pmod a$. Suppose $(as+t)$-th row ($0 \le t < s$) is the uppermost row containing a black square, and $b$ is the number of black squares lying on and above the 0-th row. If we denote by $c_l$ for $l=1, 2, \dots, a$ the remainder obtained when $\sum_{i=0}^{s+1} f(ai + l)$ is divided by $a$, then we have
$$c_l \equiv \sum_{i=0}^{s+1} g(ai+l) \equiv b-l \pmod a,$$
which shows that $\{c_1, c_2, \dots, c_a\}$ is a permutation of $\{0, 1, 2, \dots, a-1\}$. Therefore, we have
$$\sum_{y=1}^{as+t} f(y) \ge \sum_{l=1}^{a} c_l = \frac{a(a-1)}{2}.$$
Similarly, if we add the values of $f(y)$ for $y < 0$, we get the sum to be $\ge \frac{a(a-1)}{2}$ as well. Therefore, the sum taken over all regions lying inside of the vertical is greater than or equal to $a(a-1)$.

Since there are $a$ vertical lines containing $A$ we conclude that $L \ge a^2(a-1)$ and therefore, $K \le a(n+1-a)$ must hold, and this completes the proof.