Track / Stage 8 / 110 of 180 #1810 of 2000

Problem 1810

IMO Shortlist mid-range; USAMO P2/P5

Algebra Difficulty 8.4 Prove it Baltic Way 2011 Problem Shortlist · Baltic Way · 2011

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)$ .

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official 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.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.