Competition problem — Combinatorics

Library / /8 of 16

Combinatorics Difficulty 5.9 AIME, harder Prove it Brazil

Emerald writes $2009^2$ integers in a $2009 \times 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?

Solution

Yes, it is. For instance, consider the table

$(3^1 - 2)^2$	$3(2 \cdot 3^1 - 1)$	$0$	$0$	$\ldots$	$0$
$0$	$(3^2 - 2)^2$	$3(2 \cdot 3^2 - 1)$	$0$	$\ldots$	$0$
$0$	$0$	$(3^3 - 2)^2$	$3(2 \cdot 3^3 - 1)$	$\ldots$	$0$
$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$
$0$	$0$	$0$	$0$	$\ldots$	$(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^{2k} + 2 \cdot 3^k + 1 = (3^k + 1)^2

1 \le k \le 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^{2k} - 2 \cdot 3^k + 1 = (3^k - 1)^2$ , $2 \le k \le 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.

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.