IMO 1995 SL 28

Problem

S6 (IND) Let N denote the set of all positive integers. Prove that there exists a unique function f : N \toN satisfying f(m + f(n)) = n + f(m + 95) for all m and n in N. What is the value of 19 k=1 f(k)?

Solution

Let F(x) = f(x) −95 for x \geq1. Writing k for m + 95, the given condition becomes F(k + F(n)) = F(k) + n, k \geq96, n \geq1. (1) Thus for x, z \geq96 and an arbitrary y we have F(x + y) + z = F(x + y + F(z)) = F(x + F(F(y) + z)) = F(x) + F(y) + z, and consequently F(x + y) = F(x) + F(y) whenever x \geq96. Moreover, since then F(x + y) + F(96) = F(x + y + 96) = F(x) + F(y + 96) = F(x) + F(y) + F(96) for any x, y, we obtain F(x + y) = F(x) + F(y), x, y \inN. (2) It follows by induction that F(n) = nc for all n, where F(1) = c. Equation (1) becomes ck + c2n = ck + n, and yields c = 1. Hence F(n) = n and f(n) = n + 95 for all n. Finally, 19 k=1 f(k) = 96 + 97 + \cdot \cdot \cdot + 114 = 1995. Second solution. First we show that f(n) > 95 for all n. If to the contrary f(n) \leq95, we have f(m) = n + f(m + 95 −f(n)), so by induction f(m) = kn+f(m+k(95−f(n))) \geqkn for all k, which is impossible. Now for m > 95 we have f(m+f(n)−95) = n+f(m), and again by induction f(m + k(f(n) −95)) = kn + f(m) for all m, n, k. It follows that with n fixed, (\forallm) lim k\to\infty f(m + k(f(n) −95)) m + k(f(n) −95)

n f(n) −95; hence lim s\to\infty f(s) s

n f(n) −95. Hence n f(n)−95 does not depend on n, i.e., f(n) \equivcn+95 for some constant c. It is easily checked that only c = 1 is possible.