Mathematical Olympiad Rioplatense

All functions of the form $f(x)=cx$ with $c\in \mathbb{R}$ are solutions; they are the only ones. More generally let $b>a>0$, and let the open interval $\Delta =(a,b)$ contain an integer (in our case $a=10^6-10^{-6}$, $b=10^6+10^{-6}$). Consider any function $f:\mathbb{N}\to \mathbb{R}$ such that $f(x+y)=f(x)+f(y)$ holds whenever $\frac{x}{y}\in \Delta$. We prove that $f(n)=cn$ for all $n\in \mathbb{N}$ with a real constant $c$.

To begin with let us show that $f(n+1)-f(n)=f(n)-f(n-1)$ for all sufficiently large $n$. The reason is that for each sufficiently large $n\in \mathbb{N}$ there is a $z\in \mathbb{N}$ such that $$f(n+1)-f(n)=f(z+1)-f(z)=f(n)-f(n-1).$$ To ensure the first equality it is enough to take a $z$ so that $\frac{z}{n+1}\in \Delta$ and $\frac{z+1}{n}\in \Delta$. Then by hypothesis $f(x+y)=f(x)+f(y)$ will hold with $x=z$, $y=n+1$ and also with $x=z+1$, $y=n$. Hence $f(z)+f(n+1)=f(n+z+1)=f(z+1)+f(n)$, as desired. Likewise the second equality will hold provided that $\frac{z}{n}\in \Delta$ and $\frac{z+1}{n-1}\in \Delta$. Since $\frac{z}{n+1}<\frac{z}{n}<\frac{z+1}{n}<\frac{z+1}{n-1}$, it suffices to find an integer $z$ so that $a<\frac{z}{n+1}$ and $\frac{z+1}{n-1}<b$, i.e. $a(n+1)<z<b(n-1)-1$. Such an integer does exist for $n$ large enough. Indeed $b(n-1)-1$ and $a(n+1)$ differ by $(b-a)n-(a+b+1)$ which is greater than 1 for $n>\frac{a+b+2}{b-a}$.

In summary there exists a $k\in \mathbb{N}$ such that $f(n+1)-f(n)$ has the same value for all $n\ge k$. Then by standard induction $$(\ast )f(n)=(n-k)[f(k+1)-f(k)]+f(k)\text{for all }n\ge k.$$ There are $x,y\in \mathbb{N}$ such that $x,y\ge k$ and $\frac{x}{y}\in \Delta$. For instance choose a rational $\frac{r}{s}\in \Delta$ ($r,s\in \mathbb{N}$) and set $x=rk,y=sk$. Take one such pair $x,y$ and compute $f(x),f(y),f(x+y)$ by the formula $(\ast )$; this can be done because $x,y,x+y\ge k$. Replace the obtained values in $f(x+y)=f(x)+f(y)$, which holds because $\frac{x}{y}\in \Delta$. Simplification leads to $kf(k+1)=(k+1)f(k)$. Hence $\frac{f(k)}{k}=\frac{f(k+1)}{k+1}=c\in \mathbb{R}$; equivalently $f(k)=ck$ and $f(k+1)=c(k+1)$. Then $(\ast )$ takes the form $f(n)=cn$ for all $n\ge k$. It remains to show that $f(n)=cn$ for all $n\in \mathbb{N}$.

Only finitely many $n\in \mathbb{N}$ may possibly disobey $f(n)=cn$. Suppose that such values exist, and let $q$ be the greatest one of them. Choose an integer $w\in \Delta$ and set $x=wq,y=q$. Then $x/w\in \Delta$, hence $f((w+1)q)=f(wq)+f(q)$. If $w>1$ then $(w+1)q>wq>q$, so by the choice of $q$ we have $f((w+1)q)=c(w+1)q$, $f(wq)=cwq$. However then $f(q)=c(w+1)q-cwq=cq$, contrary to the assumption that $q$ violates $f(n)=cn$. And if $w=1$ then $(w+1)q=2q>q$, so $f(2q)=2cq$. On the other hand $f((w+1)q)=f(wq)+f(q)$ takes the form $f(2q)=2f(q)$ which leads to the impossible $f(q)=cq$ again. This completes the proof.

Remark. The main assumption is $f(x+y)=f(x)+f(y)$ whenever $\frac{x}{y}\in \Delta$, where $\Delta$ is an arbitrary open interval with positive endpoints. It ensures $f(n)=cn$ for all sufficiently large values of $n$. However the additional assumption that $\Delta$ contains an integer is essential to infer that $f(n)=cn$ for all $n\in \mathbb{N}$. Consider for instance the function $f:\mathbb{N}\to \mathbb{R}$ defined by $f(n)=n$ for $n\ge 5$ and $f(n)=2010$ for $n\in \{1,2,3,4\}$ (in fact $f(1),f(2),f(3),f(4)$ can be arbitrary). The interval $\Delta =(3/2,5/3)$ does not contain fractions with denominators $1,2,3,4$. So $\frac{x}{y}\in \Delta$ implies $x\ge y\ge 5$; the equation $f(x+y)=f(x)+f(y)$ is satisfied for such values. Thus $f$ is a function that satisfies the main assumption and $f(n)=n$ for $n\ge 5$ but not for all $n$.