Olympiad Maths Prep

Library / /10 of 14

Algebra Difficulty 8.1 Shortlist Prove it Romania

Determine all functions ff of the set of positive integers into itself such that f(m)mf(m) \ge m and f(m+n)f(m+n) divides f(m)+f(n)f(m) + f(n) for all positive integers mm and nn.

Solution

To this end, write =f(1)\ell = f(1), and notice that, since 1f(n)/n1 \le f(n)/n \le \ell, there exists a minimal positive integer kk \le \ell such that f(n)/n=k\lfloor f(n)/n \rfloor = k for infinitely many positive integers nn. Let AA denote the set of all these positive integers, let B={n:nA and 2nA}B = \{n: n \in A \text{ and } 2n \notin A\}, and let A=ABA' = A \setminus B.

We now show that BB is finite, so AA' is infinite. Indeed, f(2n)2f(n)f(2n) \le 2f(n) and f(2n)/(2n)2f(n)/(2n)=k\lfloor f(2n)/(2n) \rfloor \le \lfloor 2f(n)/(2n) \rfloor = k imply f(2n)/(2n)<k\lfloor f(2n)/(2n) \rfloor < k for all nn in BB, so BB is finite by minimality of kk.

Next, for nn in AA', write
2f(n)f(2n)=f(n)nf(2n)2n<1+1k, \frac{2f(n)}{f(2n)} = \frac{\frac{f(n)}{n}}{\frac{f(2n)}{2n}} < 1 + \frac{1}{k},
to deduce that the positive integer 2f(n)/f(2n)2f(n)/f(2n) is less than 22, so f(2n)=2f(n)f(2n) = 2f(n).

Further, fix a positive integer aa and notice, as before by minimality of kk, that f(a+n)k(a+n)f(a+n) \ge k(a+n) for all but finitely many nn in AA'. Hence
f(a)+f(n)f(a+n)<f(a)+(k+1)nk(a+n), \frac{f(a) + f(n)}{f(a + n)} < \frac{f(a) + (k + 1)n}{k(a + n)},
for all but finitely many nn in AA', so (f(a)+f(n))/f(a+n)(f(a) + f(n))/f(a+n) is a positive integer less than 22 for all but finitely many nn in AA', i.e., f(a+n)=f(a)+f(n)f(a+n) = f(a)+f(n) for all but finitely many nn in AA'.

Finally, fix two positive integers aa and bb. By the preceding, f(a+n)=f(a)+f(n)f(a+n) = f(a)+f(n), f(b+n)=f(b)+f(n)f(b+n) = f(b)+f(n), and (f(a+n)+f(b+n))/f(a+b+2n)(f(a+n)+f(b+n))/f(a+b+2n) is a positive integer for all but finitely many nn in AA'. Consequently,
f(a)+f(b)+2f(n)f(a+b)+f(2n)=f(a)+f(b)+f(2n)f(a+b)+f(2n) \frac{f(a) + f(b) + 2f(n)}{f(a + b) + f(2n)} = \frac{f(a) + f(b) + f(2n)}{f(a + b) + f(2n)}
is a positive integer for all but finitely many nn in AA', so the latter must equal 11 for all but finitely many nn in AA', i.e., f(a+b)=f(a)+f(b)f(a+b) = f(a)+f(b). This ends the proof.

Looking for a route rather than 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.