, 2011

For integers $x$ and $y$, by a segment $[x, y]$ we mean the set of all integers $t$ such that $x \le t \le y$; the length of this segment is $y - x$.
If, for every two positive integers $x$ and $y$ of the same colour we have $\frac{f(x)}{x} = \frac{f(y)}{y}$, then one can choose $a = \max\left\{\frac{f(r)}{r}, \frac{f(b)}{b}\right\}$, where $r$ and $b$ are arbitrary red and blue numbers, respectively. So we can assume that there are two red numbers $x$ and $y$ such that $\frac{f(x)}{x} \ne \frac{f(y)}{y}$.
Set $m = x y$. Then each segment of length $m$ contains a blue number. Indeed, assume that all the numbers on the segment $[k, k+m]$ are red. Then
$$f(k + m) = f(k + x y) = f(k + x(y - 1)) + f(x) = \dots = f(k) + y f(x), \\ f(k + m) = f(k + x y) = f(k + (x - 1)y) + f(y) = \dots = f(k) + x f(y),$$
so $y f(x) = x f(y)$, a contradiction. Now we consider two cases.

Case 1. Assume that there exists a segment $[k, k+m]$ of length $m$ consisting of blue numbers. Define $D = \max\{f(k), \dots, f(k+m)\}$. We claim that $f(z) - f(z-1) \le D$, whenever $z > k$, and the conclusion follows. Consider the largest blue number $b_1$ not exceeding $z$, so $z-b_1 \le m$, and some blue number $b_2$ in the segment $[b_1+k, b_1+k+m]$, so $b_2 > z$. Write $f(b_2) = f(b_1) + f(b_2-b_1) \le f(b_1) + D$ to deduce that $f(z+1) - f(z) \le f(b_2) - f(b_1) \le D$, as claimed.

Case 2. Each segment of length $m$ contains numbers of both colours. Fix any red number $R \ge 2m$ such that $R+1$ is blue and set $D = \max\{f(R), f(R+1)\}$. Now we claim that $f(z+1)-f(z) \le D$, whenever $z > 2m$. Consider the largest red number $r$ not exceeding $z$ and the largest blue number $b$ smaller than $r$; then $0 < z-b = (z-r)+(r-b) \le 2m$, and $b+1$ is red. Let $t = b+R+1$; then $t > z$. If $t$ is blue, then $f(t) = f(b)+f(R+1) \le f(b)+D$, and $f(z+1)-f(z) \le f(t)-f(b) \le D$. Otherwise, $f(t) = f(b+1)+f(R) \le f(b+1)+D$, hence $f(z+1)-f(z) \le f(t)-f(b+1) \le D$, as claimed.