Maths Olympiad Prep

Library / /77 of 133

, 2015

Algebra Difficulty 5.7 AIME, harder Prove it Saudi Arabia

Find all strictly increasing functions f:ZRf: \mathbb{Z} \rightarrow \mathbb{R} such that for any m,nZm, n \in \mathbb{Z} there exists a kZk \in \mathbb{Z} such that f(k)=f(m)f(n)f(k)=f(m)-f(n).

Solution

Let f:ZRf: \mathbb{Z} \rightarrow \mathbb{R} be such a function. We prove that f(n+1)f(n)f(n+1)-f(n) is a positive constant aa independent of the integer nn.

Indeed, assume that there exist two integers n0,n1n_{0}, n_{1} such that
f(n0+1)f(n0)<f(n1+1)f(n1). f\left(n_{0}+1\right)-f\left(n_{0}\right)<f\left(n_{1}+1\right)-f\left(n_{1}\right) .
Let k0,k1k_{0}, k_{1} be integers such that f(k0)=f(n0+1)f(n0)f\left(k_{0}\right)=f\left(n_{0}+1\right)-f\left(n_{0}\right) and f(k1)=f(n1+1)f(k0)f\left(k_{1}\right)= f\left(n_{1}+1\right)-f\left(k_{0}\right). Because ff is strictly increasing, f(k0)>0f\left(k_{0}\right)>0. We deduce that f(n1)<f(k1)=f(n1+1)f(k0)<f(n1+1)f\left(n_{1}\right)<f\left(k_{1}\right)=f\left(n_{1}+1\right)-f\left(k_{0}\right)<f\left(n_{1}+1\right), which is impossible since ff is strictly increasing and n1,n1+1n_{1}, n_{1}+1 are consecutive integers.

Moreover, there exists an integer n0n_{0} such that f(n0)=f(0)f(0)=0f\left(n_{0}\right)=f(0)-f(0)=0.
Let n>n0n>n_{0}. We have
f(n)=f(n0)+m=0nn01(f(n0+m+1)f(n0+m))=a(nn0). f(n)=f\left(n_{0}\right)+\sum_{m=0}^{n-n_{0}-1}\left(f\left(n_{0}+m+1\right)-f\left(n_{0}+m\right)\right)=a\left(n-n_{0}\right) .
We obtain a similar formula for n<n0n<n_{0} and therefore
f(n)=a(nn0), for all nZ. f(n)=a\left(n-n_{0}\right), \quad \text{ for all } n \in \mathbb{Z} .
Conversely, let a>0a>0 be a positive real number and n0n_{0} an integer and define f(n)=a(nn0)f(n)=a\left(n-n_{0}\right) for all nZn \in \mathbb{Z}. The function ff is strictly increasing and for any integers m,nZm, n \in \mathbb{Z} we have f(m)f(n)=f(mn+n0)f(m)-f(n)=f\left(m-n+n_{0}\right).

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.