Library / /14 of 69

, 2011

Algebra Difficulty 4.6 AIME Prove it South Africa

Let $\{a_1, a_2, ..., a_m\}$ and $\{b_1, b_2, ..., b_n\}$ be two sets of reals with the same sum. Prove that you can find an $m \times n$ array so that the row sums are $a_1, a_2, ..., a_m$ and the column sums are $b_1, b_2, ..., b_n$ .

Solution

Let $S = \sum a_i = \sum b_i$ , and let $\omega = a_n + b_n - S$ . Create the table

0	0	...	0	$a_1$
0	0	...	0	$a_2$
...	...	...	...	...
$b_1$	$b_2$	...	$b_{n-1}$	$\omega$

The sum of the first

m-1

rows and

n-1

columns clearly satisfies the conditions, and the last row sum is

b_1 + b_2 + ... + b_{n-1} + \omega = \sum b_i + a_n - S = a_n

as required. Likewise for the last column sum.

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.