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
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.
29.08.2014 23:03
I'm not sure why $a_{ij}\ge0$ in your solution. Anyway, here is mine:
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$.
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.
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$.