Show that it is possible to write a $n \times n$ array of non-negative numbers (not necessarily distinct) such that the sums of entries on each row and each column are pairwise distinct perfect squares.
Problem
Source: Saudi Arabia IMO TST Day II Problem 3
Tags: induction, algebra, system of equations, number theory unsolved, number theory
cobbler
23.07.2014 05:06
Let the array of numbers have the entry $a_{ij}$ in the ith row and jth column. Let $a_{1j}=0$ for $j=1,2,...,n$. The equalities are: $\sum_{j=1}^n a_{ij} = x_i^2$ and $\sum_{j=1}^n b_{ij} = y_i^2$ for $i=1,2,...,n$. (*) Adding up and observing the equality of the overall sum of rows and columns (each being the sum of all entries in the array), we see that: $\sum_{i=1}^n x_i^2 = \sum_{i=1}^n y_i^2$. However, since $a_{1j}=0\ \forall j\in \mathbb{N}$ it follows that $\sum_{i=2}^n x_i^2 = \sum_{i=1}^n y_i^2$. We will prove that this is always possible for $x_i,y_i$ all distinct, and once we prove this the result will follow since we can pick non-distinct $a_{ij},b_{ij}$ to solve the system of equations in (*). Proof. By the Pythagoras, we can always find $x,y,z$ distinct such that $x^2+y^2=z^2$. We can also find another triple distinct from this such that $a^2+b^2=c^2$, making sure that $b,y,n$ for some positive integer $n$ is another pythagorean triple. (This last part is proven below as a lemma.) Adding yields $x^2+y^2+a^2+b^2=c^2+z^2$ or $x^2+n^2+a^2=c^2+z^2$, and applying this repeatedly by adding a new triple each time yields the result. Lemma. We prove it is possible to find pythagorean triples $a^2+b^2=c^2$ and $x^2+y^2=z^2$ such that $b^2+y^2$ is a perfect square. This is how you do it: Pick a large primitive triple b,y,n such that b is a multiple of 3 and y is a multiple of 4 (this is always possible, just take $r=6r_1+4$ and $s=3s_1+1$ with $(r,s)=1$). Now take 3,4,5 and multiple each term by m to get (3m,4m,5m) such that 3m=b, and take the other triple as (3n,4n,5n) such that 4n=y.
Radar
29.08.2014 23:03
I'm not sure why $a_{ij}\ge0$ in your solution. Anyway, here is mine:
For $n=1$ the claim is obviously false. Lets prove it by induction for $n>1$. For $n=2$ we can use for example
0 1
16 48
Now suppose we have such a table $T$ for $(n-1)\times (n-1)$ and we'll create table $T'$ for $n\times n$. If there is a number in $T$ not divisible by 4, we multiply all the numbers in the table by 4 (it will obviously keep working). Under every column we write its sum multiplied by $a^2-1$ and next to every row it sum its sum multiplied by $b^2-1$ for some big enough, distinct $a$ and $b$, such that in $T$ there is now row with sum $r^2$ and column with sum $c^2$ such that $ac=br$. It obvious that we can have $a$ and $b$ arbitrarily big. Now lets put this in the table $T'$. We see that there is no number in down-right corner, so we put there $t=s_1^2+s_2^2+1-2s_1-2s_2-2s_1s_2$, where $4s_1$, resp. $4s_2$ is sum of all numbers except $t$ in the bottom row, resp. rightmost column (they are divisible by 4, because every number in $T$ is divisible by four and these are just some sums and multiplies). That means that for
0 1
16 48
we would first do
0 4
64 192
then (we'd choose $a=2$, $b=3$)
0 4 32
64 192 2048
192 588
which means $s_1=195$ and $s_2=520$, so $T'$ is
0 4 32
64 192 2048
192 588 104196
Well, now why it works. We can choose $a$ hugely bigger than $b$, so we get $s_1\ge 2s_2+2$. Therefore $t=(s_2^2+1-2s_2)+s_1(s_1-2s_2-2)\ge0$ and it's obvious all other numbers in the table are nonnegative. Now every column except last one has $a^2$ times bigger sum than it had in $T$, so it's still a square. Analogically for rows. Last column has sum $(s_1^2+s_2^2+1-2s_1s_2-2s_1-2s_2)+4s_2=(s_1-s_2+1)^2$. Last row has sum $(s_1-s_2-1)^2$. Obviously they are not equal and because $a$ and $b$ are huge, they are huge too, so they are bigger than other sums of rows or columns. No other two columns are equal, because they are just $a^2$ times bigger than before and analogically for rows. Finally, no column and row, from which none is bottom or rightmost, are egual, because otherwise we'd have $ac=br$, where $c^2$ and $r^2$ are the sums of corresponding column and row from $T$, which is not possible by definition of $a$ and $b$.
Q.E.D.
cobbler
04.09.2014 19:36
Radar wrote: I'm not sure why $a_{ij}\ge0$ in your solution. Care to elaborate? I only say $\sum_{j=1}^n a_{ij}= x_i^2$($\ge 0$); no where do I say $a_{ij}\ge 0$.
Radar
04.09.2014 19:51
arkanm wrote: Care to elaborate? I only say $\sum_{j=1}^n a_{ij}= x_i^2$; no where do I say $a_{ij}\ge 0$. Well, you didn't. But the problem is to fill the table with nonnegative numbers, so it has to be true for correct solution.
cobbler
04.09.2014 21:18
Right, that makes more sense. I suppressed the proof, regarding it as obvious. Once we have established the distinct perfect squares, we only need to solve equalities of the form $a^2=\sum_{i=1}^m a_i$. (This follows directly from the construction via Pythagorean triples.) This is always possible in non-distinct nonnegative integers, since we can take e.g. $a_i=0$ for $i=1,2,3,...,m-1$ and $a_m=a^2$.