Library / /25 of 33

, 2011

Algebra Difficulty 8.4 Shortlist Prove it Baltic Way

Find all functions $f$ from the set of all positive integers to the same set such that, for all positive integers $a_1, \dots, a_k$ with $k > 0$ , the sum $a_1 + \dots + a_k$ divides the sum $f(a_1) + \dots + f(a_k)$ .

Solution

Answer: All functions given by $f(n) = an$ , $a \in \mathbb{N}$ .

Suppose that $f$ is a function that satisfies the conditions of the problem. We claim that $f(n) = f(n-1) + f(1)$ for all integers $n > 1$ . Indeed, for any integer $m > n$ , we have $m \mid f(n) + f(m-n)$ and $m \mid f(n-1) + f(1) + f(m-n)$ by conditions of the problem. Hence the difference $f(n) - (f(n-1) + f(1))$ is also divisible by $m$ . As $m$ was arbitrary, this implies that $f(n) - (f(n-1) + f(1))$ is divisible by an infinite number of different integers, i.e., is equal to $0$ . This completes the proof of the claim.

Easy induction now gives that necessarily $f(n) = n f(1)$ . It remains to verify that all functions of the form $f(n) = a n$ satisfy the conditions of the problem, which is straightforward.

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.