Maths Olympiad Prep

Library / /122 of 133

Combinatorics Difficulty 7.0 National olympiad, round 2 Prove it Saudi Arabia

Show that it is possible to write a n×nn \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.

Solution

First solution suggested by the student Salman Saleh. We will construct an n×nn \times n array by induction on n≥2n \geq 2.
For n=2n=2, consider the following example:

09
016
Assume there exists an n×nn \times n array
a1,1a_{1,1}a1,2a_{1,2}…\ldotsa1,na_{1, n}
a2,1a_{2,1}a2,2a_{2,2}…\ldotsa2,na_{2, n}
⋮\vdots⋮\vdots⋱\ddots⋮\vdots
an,1a_{n, 1}an,2a_{n, 2}…\ldotsan,na_{n, n}
such that the sums of entries on each row and each column are pairwise distinct perfect squares and such that the sum of the last column is greater than all the other sums. Let
ri2=∑j=1nai,j, for i=1,2,…,n r_{i}^{2}=\sum_{j=1}^{n} a_{i, j}, \text{ for } i=1,2, \ldots, n
and
cj2=∑i=1nai,j, for j=1,2,…,n, c_{j}^{2}=\sum_{i=1}^{n} a_{i, j}, \text{ for } j=1,2, \ldots, n,
be the distinct perfect squares. Notice that
∑i=1nri2=∑j=1ncj2 \sum_{i=1}^{n} r_{i}^{2}=\sum_{j=1}^{n} c_{j}^{2}
Consider the following (n+1)×(n+1)(n+1) \times(n+1) array
4a1,14 a_{1,1}4a2,14 a_{2,1}…4an,14 a_{n, 1}12c1212 c_{1}^{2}
4a1,24 a_{1,2}4a2,24 a_{2,2}…4an,24 a_{n, 2}12c2212 c_{2}^{2}
⋮\vdots⋮\vdots⋱\ddots⋮\vdots⋮\vdots
4a1,n−14 a_{1, n-1}4a2,n−14 a_{2, n-1}…4an,n−14 a_{n, n-1}12cn−1212 c_{n-1}^{2}
4a1,n4 a_{1, n}4a2,n4 a_{2, n}⋯\cdots4an,n4 a_{n, n}4(25n2−1)cn24\left(25 n^{2}-1\right) c_{n}^{2}
12r1212 r_{1}^{2}12r2212 r_{2}^{2}…12rn212 r_{n}^{2}xnx_{n}
where
xn=((25n2−4)cn2−1)2−12∑i=1nri2. x_{n}=\left(\left(25 n^{2}-4\right) c_{n}^{2}-1\right)^{2}-12 \sum_{i=1}^{n} r_{i}^{2} .
Notice that
xn>((25n2−4)cn2−1)2−12ncn2>(21n2−4)cn2>0. x_{n}>\left(\left(25 n^{2}-4\right) c_{n}^{2}-1\right)^{2}-12 n c_{n}^{2}>\left(21 n^{2}-4\right) c_{n}^{2}>0 .
The sums of entries of each row and each columns are
(4c1)2,(4c2)2,…,(4cn−1)2,(4r1)2,(4r2)2,…,(4rn)2, \left(4 c_{1}\right)^{2},\left(4 c_{2}\right)^{2}, \ldots,\left(4 c_{n-1}\right)^{2},\left(4 r_{1}\right)^{2},\left(4 r_{2}\right)^{2}, \ldots,\left(4 r_{n}\right)^{2},
which are all distinct and less than the three other sums
(10ncn)2<((25n2−4)cn2−1)2<((25n2−4)cn2+1)2, \left(10 n c_{n}\right)^{2}<\left(\left(25 n^{2}-4\right) c_{n}^{2}-1\right)^{2}<\left(\left(25 n^{2}-4\right) c_{n}^{2}+1\right)^{2},
and clearly, the sum of the last column is the greatest perfect square.

Second solution suggested by the student Alhamza Alnufayli. If n=2k≥2n=2 k \geq 2, we consider the following n×nn \times n array:

48⋅22(k−1)48 \cdot 2^{2(k-1)}0⋯\cdots00⋯\cdots033⋅22(k−1)33 \cdot 2^{2(k-1)}
0⋱\ddots⋱\ddots⋮\vdots⋮\vdots⋅\cdot⋅\cdot0
⋮\vdots⋱\ddots48⋅2248 \cdot 2^{2}0033⋅2233 \cdot 2^{2}⋅\cdot⋮\vdots
0⋯\cdots048330⋯\cdots0
0⋯\cdots0130⋯\cdots0
⋮\vdots⋅\cdot222^{2}003⋅223 \cdot 2^{2}⋱\ddots⋮\vdots
0⋅\cdot⋅\cdot⋮\vdots⋮\vdots⋱\ddots⋱\ddots0
22(k−1)2^{2(k-1)}0⋯\cdots00⋯\cdots03⋅22(k−1)3 \cdot 2^{2(k-1)}
The sums of entries of each row and each column are
(9⋅2k−1)2,…,(9⋅2)2,(9⋅1)2,(2⋅1)2,(2⋅2)2,…,(2⋅2k−1)2,(7⋅2k−1)2,…,(7⋅2)2,(7⋅1)2,(6⋅1)2,(6⋅2)2,…,(6⋅2k−1)2, \begin{aligned} & \left(9 \cdot 2^{k-1}\right)^{2}, \ldots,(9 \cdot 2)^{2},(9 \cdot 1)^{2},(2 \cdot 1)^{2},(2 \cdot 2)^{2}, \ldots,\left(2 \cdot 2^{k-1}\right)^{2}, \\ & \left(7 \cdot 2^{k-1}\right)^{2}, \ldots,(7 \cdot 2)^{2},(7 \cdot 1)^{2},(6 \cdot 1)^{2},(6 \cdot 2)^{2}, \ldots,\left(6 \cdot 2^{k-1}\right)^{2}, \end{aligned}
which are all distinct perfect squares.
If n=2k+1≥2n=2 k+1 \geq 2, we consider the following n×nn \times n array:
48⋅22(k−1)48 \cdot 2^{2(k-1)}0⋯\cdots000⋯\cdots033⋅22(k−1)33 \cdot 2^{2(k-1)}
0⋱\ddots⋱\ddots⋮\vdots⋮\vdots⋮\vdots⋅\cdot⋅\cdot0
⋮\vdots⋱\ddots48⋅2248 \cdot 2^{2}00033⋅2233 \cdot 2^{2}⋅\cdot⋮\vdots
0⋯\cdots048360330⋯\cdots0
0⋯\cdots⋯\cdots013213^{2}0⋯\cdots⋯\cdots0
0⋯\cdots01030⋯\cdots0
⋮\vdots⋅\cdot222^{2}0003⋅223 \cdot 2^{2}⋱\ddots⋮\vdots
0⋅\cdot⋅\cdot⋮\vdots⋮\vdots⋱\ddots⋱\ddots0
22(k−1)2^{2(k-1)}0⋯\cdots000⋯\cdots03⋅22(k−1)3 \cdot 2^{2(k-1)}
The sums of entries on each row and each column are
(9⋅2k−1)2,…,(9⋅2)2,212,132,(2⋅1)2,(2⋅2)2,…,(2⋅2k−1)2(7⋅2k−1)2,…,(7⋅2)2,(7⋅1)2,232,(6⋅1)2,(6⋅2)2,…,(6⋅2k−1)2 \begin{gathered} \left(9 \cdot 2^{k-1}\right)^{2}, \ldots,(9 \cdot 2)^{2}, 21^{2}, 13^{2},(2 \cdot 1)^{2},(2 \cdot 2)^{2}, \ldots,\left(2 \cdot 2^{k-1}\right)^{2} \\ \left(7 \cdot 2^{k-1}\right)^{2}, \ldots,(7 \cdot 2)^{2},(7 \cdot 1)^{2}, 23^{2},(6 \cdot 1)^{2},(6 \cdot 2)^{2}, \ldots,\left(6 \cdot 2^{k-1}\right)^{2} \end{gathered}
which are all distinct perfect squares.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.