The numbers $1, 2, \ldots 49$ are placed in a $7\times 7$ array, and the sum of the numbers in each row and in each column is computed. Some of these $14$ sums are odd while others are even. Let $A$ denote the sum of all the odd sums and $B$ the sum of all even sums. Is it possible that the numbers were placed in the array in such a way that $A = B$?
Problem
Source: Baltic Way 2001
Tags: combinatorics proposed, combinatorics
17.11.2010 21:49
Note that $A+B=2(1+2+...+49)$ since $A+B$ is the sum of all rows and columns and all numbers are counted twice. If $A=B$, then $A=B=1+2+...+49=49\times 25$ which is odd, but $B$ is even since it is the sum of even rows and columns. Contradiction.It is not possible.
07.12.2021 00:23
Can we do it for any integer n?can the problem be generalised ?
30.03.2022 18:12
For a general $n$, we have $A+B=2(1+2+\ldots+n^2)$; if $A=B$, since $B$ is even, we have that $A+B=2B$ is a multiple of $4$, therefore $(1+2+\ldots+n^2)$ must be even. Therefore for all odd numbers it's impossible for the same reason it's impossible for $n=7$: $(1+2+\ldots+n^2)$ is odd. For even numbers of the form $n=4k+2$ the standard placing of $1,2,\ldots, n^2$ fulfills the condition: the rows' sums are odd since each row has $2k+1$ odd numbers, while the columns' sums are even since they have either $4k+2$ odd numbers or $4k+2$ even numbers. Since summing all rows equals summing all columns, we have $A=B=(1+2+\ldots+n^2)$. For example, for $n=2$ we have $\begin{pmatrix} 1 & 2 \\ 3 & 4\end{pmatrix}$ and $A=B=10$. For even numbers of the form $4k$, consider the standard placement but with the last row reversed; for example for $n=4$, we have $\begin{pmatrix} 1 & 2 & 3 & 4\\ 5 & 6 & 7 & 8\\ 9 & 10 & 11 & 12 \\ 16 & 15 & 14 & 13 \end{pmatrix}$ This time all rows' sums are even since they have $2k$ odd numbers and all columns' sums are odd since they have either $1$ or $4k-1$ odd numbers; therefore just like in the previous case, $A=B=(1+2+\ldots+n^2)$.