Is it possible to fill the $121$ entries in an $11\times11$ square with the values $0,+1,-1$, so that the row sums and column sums are $22$ distinct numbers?
Answer
I've found a solution here, which I've decided to blatantly steal since I think a lot of people really want to see a fully worked out solution. It is indeed impossible. The same method below can be used to show that a valid $n\times n$ matrix can only exist if $n$ is even and the missing sum is $\pm n$.
Let's say the missing sum is $m$. We can assume by symmetry that $m\le 0$. There are 11 rows and columns whose sum is positive. Let's rearrange these positive row/columns so that they are all on the top/left of the matrix. Assuming there are $r$ positive rows, this means there are $11-r$ positive columns. Let's group all the positive columns on the left, and all positive rows on top. See the picture at the bottom, where I've given labels A, B, C and D to four quadrants of the matrix.
Now, let $a$ be the sum of the numbers in section A, and the same with $b,c,d$. Then $$\begin{align} a+b+c+d &=(\text{sum of all rows and columns})/2\\ &=((-11)+(-10)+\dots+11-m)/2\\ &=-m/2 \end{align}$$ We also know that $$ \begin{align} (a+b)+(a+c) &=\text{sum of all positive rows/columns}\\ &=1+2+\dots+11\\ &=66 \end{align}$$ Combining these last two observations, $$ -m/2=a+b+c+d=(2a+b+c)-a+d=66-a+d $$ Here's the kicker. There are $r(11-r)$ entries in section $A$, meaning that $a\le r(11-r)$. No matter what $r$ is, the quantity $r(11-r)$ is at most $30^*$. Similarly, $d\ge -30$. This means that $$ -m/2\ge 66-30-30=6, $$ implying that $m\le -12$, a contradiction.
${}^*$ To make this proof to work for a general $n\times n$ matrix, instead of just $n=11$, use the inequality $ab\le (a+b)^2/4$, which shows $r(n-r)\le n^2/4$. We then get that $-m/2=\frac{n(n+1)}2-a+d\ge \frac{n(n+1)}2-\frac{n^2}4-\frac{n^2}4=n/2$, implying that $m\le -n$, which means $m=-n$. Since the missing sum must be even, this means $n$ must be even.
No comments:
Post a Comment