Competition problem — Combinatorics

Library / /9 of 15

Combinatorics Difficulty 5.1 AIME, harder Prove it United States

Problem:
A $2012 \times 2012$ table is to be filled with integers in such a way that each of the 4026 rows, columns, and main diagonals has a different sum. What is the smallest number of distinct values that must be used in the table?

Solution

Solution:
Answer: 3.
If at most two numbers are used, say $x$ and $y$ , the sum of every row and column is completely determined by the number of $y$ 's it has, which ranges from 0 to 2012. Thus there are only 2013 possible sums, not enough for the 4026 rows, columns, and diagonals.

On the other hand, if $n$ is a large integer (say, 10000), then it is possible to fill the table using 0, 1, and $n$ . Here is a $6 \times 6$ example that generalizes readily:

1	0	0	0	0	0
1	1	0	0	0	$n$
1	1	1	0	$n$	$n$
1	1	0	$n$	$n$	$n$
1	0	0	0	$n$	$n$
0	0	0	0	0	$n$

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 reproduced verbatim; metadata (topic, difficulty) added by this project.