XXXI Brazilian Math Olympiad

Question

Emerald writes 2009^2 integers in a 2009 2009 table, one number in each entry of the table. She sums all the numbers in each row and in each column, obtaining 4018 sums. She notices that all sums are distinct. Is it possible that all such sums are perfect squares?

Accepted Answer

Yes, it is. For instance, consider the table

$(3^{1} - 2)^{2}$	$3 (2 \cdot 3^{1} - 1)$	$0$	$0$	$\dots$	$0$
$0$	$(3^{2} - 2)^{2}$	$3 (2 \cdot 3^{2} - 1)$	$0$	$\dots$	$0$
$0$	$0$	$(3^{3} - 2)^{2}$	$3 (2 \cdot 3^{3} - 1)$	$\dots$	$0$
$\dots$	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$
$0$	$0$	$0$	$0$	$\dots$	$(3^{2009} - 2)^{2}$

The sum of the numbers in each row except the last one is

(3^{k} - 2)^{2} + 3 (2 \cdot 3^{k} - 1) = 3^{2 k} + 2 \cdot 3^{k} + 1 = (3^{k} + 1)^{2}

,

1 \leq k \leq 2008

, and the sum of the numbers in the last row is

(3^{2009} - 2)^{2}

.

The sum of the numbers in each column except the first one is

3 (2 \cdot 3^{k - 1} - 1) + (3^{k} - 2)^{2} = 3^{2 k} - 2 \cdot 3^{k} + 1 = (3^{k} - 1)^{2}

,

2 \leq k \leq 2009

, and the sum of the numbers in the first column is

1

.

Note that all 4018 sums are distinct perfect squares, so we are done.