Let $k$ and $n$ be two positive integers such that $k<n$ and $k$ does not divide $n$. Show that one can fill a $n \times n$ square grid with $n^2$ real numbers such that sum of numbers in an arbitrary $k \times k$ square grid is negative, but sum of all $n^2$ numbers is positive.

Source: Homework

My idea: I presented $n = mk + r$ and write $-k^2$ into each square with coordinate of the form $(ik, jk)$ where $i, j$ are positive integers and 1 in another squares. Then the sum of each $k \times k$ square is $-1$ and sum of $n^2$ numbers is $n^2 - m^2(k^2+1)$. But this doesn't work for large $m$.

| cite | improve this question | | | | |
  • 1
    $\begingroup$ Note that the fact that the entries have to be real does not add any extra possibilities over just taking integer values: If we have a real solution we can slightly perturb the solution to make all the values rational (because it is a finite grid and all the sums of interest are elements of the open sets $\Bbb R^+$, $\Bbb R^-$), and then clear denominators to make it integral. $\endgroup$ – Mario Carneiro Oct 20 '15 at 15:23
  • $\begingroup$ So, for a $3\times3$ grid, would $\begin{array}&1&0&1\\0&-2&0\\1&0&1\end{array}$ work? $\endgroup$ – Akiva Weinberger Oct 20 '15 at 16:09
  • $\begingroup$ @AkivaWeinberger Yes, it does work. $\endgroup$ – primitiveroot Oct 20 '15 at 16:14

This can be done so that all rows are the same. Here's the idea of my solution: let the first column all have a value of $a > 0$, to be chosen later. Let the next $k - 1$ columns all have $-1$ in them. Then repeat this pattern: one column of $a$'s, $k-1$ column's of $-1$'s. Then every $k \times k$ square has exactly one column of $a$'s and the rest are $-1$'s. Thus, the sum over this square is $ ka - k(k-1)$. If we want this value to be negative, then we need $a < k - 1$, i.e. $a = k-1 - \epsilon$ for some $\epsilon > 0$, to be decided later.

Now let's look at the sum over the whole matrix. If we write $n = mk + r$, then we have $m$ columns of $a$'s and $n - m$ columns of $-1$'s. The total sum is then $$ nma - (n - m)n$.

Note that $n = mk + r \implies n - m = m(k - 1) + r$. Thus, we have that the sum over the whole matrix is $$ nm((k - 1) - \epsilon) - ((k - 1)m - r)n = rn - nm\epsilon.$$

Thus, if we take $\epsilon = \frac{r}{2m}$, then we have that the sum is $$ rn - nm\epsilon = rn - nm \frac{r}{2m} = \frac{rn}{2} > 0$$ as desired.

EDIT: The final matrix looks like: $$ \left(\begin{array}{cccc|cccc|c|ccc} a& -1 & \cdots & -1 &a & -1 & \cdots & -1 &\cdots &a & \cdots & -1 \\ a& -1 & \cdots & -1 &a & -1 & \cdots & -1 &\cdots &a & \cdots & -1 \\ \vdots& \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots &\ddots &\vdots & \ddots & \vdots \\ a& -1 & \cdots & -1 &a & -1 & \cdots & -1 &\cdots &a & \cdots & -1 \\ \end{array} \right)$$

Where $a = k-1 -\frac{r}{2m}$ in each block but the last I have one column of $a$'s and $(k-1)$ columns of $-1$'s. In the last column, I have $r$ $-1$'s. note, if I multiply the whole matrix by $2m$, then it has integer entries.

| cite | improve this answer | | | | |
  • $\begingroup$ As I suggested above, this can be turned into an integer solution: let every $k$-th column be $2m(k-1)-r$ and the other columns be $-2m$, in which case the sum over $k\times k$ is $-kr$ and the sum over $n\times n$ is $mnr$. $\endgroup$ – Mario Carneiro Oct 20 '15 at 15:37
  • $\begingroup$ I am afraid that you've made a little mistake in calculation. You wrote $nm((k - 1) - \epsilon) - ((k - 1)m - r)n = rn - nm\epsilon$ But I think it supposed to be $nm((k - 1) - \epsilon) - ((k - 1)m + r)n = -rn - nm\epsilon$ (since $n-m = (k-1)m + r$) and therefore the sum is $-rn - mn\epsilon$, which is clearly to be negative $\endgroup$ – primitiveroot Oct 20 '15 at 15:43
  • $\begingroup$ @MarioCarneiro, yes this is true. I added that to the solution. $\endgroup$ – Marcus M Oct 20 '15 at 15:43
  • $\begingroup$ @primitiveroot, where? $\endgroup$ – Marcus M Oct 20 '15 at 15:44
  • 1
    $\begingroup$ I also made some calculation. The sum of $n^2$ numbers are $nk - n(m+1)\epsilon$ therefore $\epsilon < \dfrac{k}{m+1}$ will work. And your idea was brilliant. Thank you! $\endgroup$ – primitiveroot Oct 20 '15 at 16:27

Here's an answer to show that in fact the OP's original idea works, if the numbers are chosen correctly.

Let our matrix take values $b-a$ at indexes $(ik,jk)$ and $b$ elsewhere, with $n$ factored as $n=mk+r$. Then the sum across a $k\times k$ submatrix is $k^2b-a$, and the sum across the whole $n\times n$ matrix is $n^2b-m^2a$. The constraints to satisfy are thus $n^2b>m^2a$ and $k^2b<a$. This implies $m^2k^2b<m^2a<n^2b$, so $mk<n$ implies $b>0$. Dividing through by $m^2b$, we get

$$k^2<\frac ab<\frac{n^2}{m^2},$$

and we can feel free to choose $b=2m^2$ and $a=n^2+m^2k^2$ (the midpoint) or any other solution which satisfies the inequality. The OP's choice used $b=1$ and $a=k^2+1$, which satisfies the first inequality, but the second inequality in the worst case has $r=1$ so $\frac nm=k+\frac1m$ and $\frac{n^2}{m^2}=k^2+2\frac km+\frac1{m^2}$, so the $+1$ is a bit too generous and is undercut for large $m$. (This can also be taken as a proof that a sufficiently large integer solution cannot take $1$ for the "background" value $b$.)

| cite | improve this answer | | | | |

This is a slight variant on the construction in Marcus M's answer.

Having written $n=mk+r$ with positive integers $m$ and $0\lt r\lt k$, start with a matrix of the form

$$\pmatrix{ a&-1&\ldots&-1&\ldots&a&-1&\ldots&-1&b&\ldots&b\\ a&-1&\ldots&-1&\ldots&a&-1&\ldots&-1&b&\ldots&b\\ \vdots\\ a&-1&\ldots&-1&\ldots&a&-1&\ldots&-1&b&\ldots&b\\ }$$

where each row consists of an $a$ followed by $(k-1)$ $-1$'s, repeated $m$ times, with $r$ $b$'s at the end. Note that the sum of any $k$ consecutive numbers in any row is either $a-(k-1)$ or $bs-(k-s)$ with $1\le s\le r$, while the sum of the entire row is $m(a-(k-1))+br$.

Next, let $a=k-1$ and $b={k\over r}-1$. The assumption $0\lt r\lt k$ implies $a$ and $b$ are both positive. Our construction so far implies that the sum of any $k$ consecutive numbers in any row is either $$a-(k-1)=(k-1)-(k-1)=0$$ or $$bs-(k-s)=({k\over r}-1)s-(k-s)={s\over r}k-k\le0$$

while the sum of all the numbers in a row is

$$m(a-(k-1))+br=m((k-1)-(k-1))+({k\over r}-1)r=k-r\ge1$$

Thus the sum of the numbers in any $k\times k$ block is less than or equal to $0$, while the sum of the entire $n\times n$ matrix is greater than or equal to $n$.

Now this isn't quite what's required, but it's easy to fix it: Just subtract a very small number (anything less than $1/n$ will do) from every number in the matrix, including all the $-1$'s. Doing so ensures that every $k\times k$ block now has a negative sum while the sum for the entire matrix is still positive.

| cite | improve this answer | | | | |

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.