Library / /8 of 45

, 2008

Number theory Difficulty 5.0 AIME Prove it Slovenia

Let $a_1, a_2, \dots, a_n$ be positive integers. Assume that for some positive integer $k$ , $k < n$ , the following is true: if we choose any $k$ of the given $n$ numbers their sum is divisible by $n$ . Prove that $a_1 + a_2 + \dots + a_n$ is also divisible by $n$ .

Solution

If $k = 1$ , each of the numbers $a_1, a_2, \dots, a_n$ is divisible by $n$ , so $n$ also divides their sum.

Now, let $1 < k < n$ and let $i \neq j$ . Since the set $\{a_1, a_2, \dots, a_n\} \setminus \{a_i, a_j\}$ has $n-2 \ge k-1$ elements, one can choose an arbitrary subset $S$ with $k-1$ elements. Then $S \cup \{a_i\}$ and $S \cup \{a_j\}$ are two $k$ -tuples of numbers and their sums are divisible by $n$ , so the difference of the two sums must also be divisible by $n$ . This difference is equal to $a_i - a_j$ , so $n$ divides $a_i - a_j$ . Here $i$ and $j$ were chosen arbitrarily, so $a_1, a_2, \dots, a_n$ give the same remainder when divided by $n$ , and there are $n$ of them, so their sum must be divisible by $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 and solution reproduced as published; topic and difficulty added by this site.