# Write $n^2$ real numbers into $n \times n$ square grid

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

• 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. – Mario Carneiro Oct 20 '15 at 15:23
• So, for a $3\times3$ grid, would $\begin{array}&1&0&1\\0&-2&0\\1&0&1\end{array}$ work? – Akiva Weinberger Oct 20 '15 at 16:09
• @AkivaWeinberger Yes, it does work. – 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. • 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. – Mario Carneiro Oct 20 '15 at 15:37 • 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 – primitiveroot Oct 20 '15 at 15:43 • @MarioCarneiro, yes this is true. I added that to the solution. – Marcus M Oct 20 '15 at 15:43 • @primitiveroot, where? – Marcus M Oct 20 '15 at 15:44 • 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! – 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.) 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.