Iranian Mathematical Olympiad

Let $D_i = \text{gcd}(a_1, \dots, a_{i-1}, a_{i+1}, \dots, a_k)$ ($i = 1, \dots, k$). Then $f(x) = Cx + f_1(x) + \dots + f_k(x)$ such that $f_1, \dots, f_k$ are periodic of period $D_i$ and $f_i(0) = 0$. Let $P = a_1 \dots a_k$ then if $f(P) = 0$ it follows that for all $i \neq j$ and $m \ge 0$ we have $f(ma_i a_j) = 0$. Indeed, letting $M = f(a_1 a_2)$ then $f(2a_1 a_2) = 2M$, $f(3a_1 a_2) = 3M$. By induction we find $f(ma_1 a_2) = mM$. Choose $m = a_2 \dots a_k$ we are done.
Let $g(x) = f(x) - \frac{x f(P)}{P}$ it follows that $g(P) = 0$ and therefore, for all $i \neq j$, $m \ge 0$ we have $g(ma_i a_j) = 0$. Writing $C = \frac{f(P)}{P}$ it follows that $f(x) = Cx + g(x)$.
If for a given $i$ we have $\sum_{j=1}^{k} u_j a_j \equiv \sum_{j=1}^{k} v_j a_j \pmod{D_i}$ with $u_i \ge 0$, $v_i \ge 0$ then $g(u_i a_i) = g(v_i a_i)$. It suffices to prove it for $i = 1$. Indeed, the congruence implies that $u_1 a_1 \equiv v_1 a_1 \pmod{D_1}$, since $\text{gcd}(a_1, D_1) = 1$ we conclude that $u_1 \equiv v_1 \pmod{D_1}$. Since $D_1 = \text{gcd}(a_2, \dots, a_k)$, write
$$v_1 - u_1 = \sum_{j=2}^{k} w_j a_j$$
where $w_j = c_j - c'_j$, $c_j, c'_j \ge 0$. Thus,
$$u_1 + \sum_{j=2}^{k} c_j a_j = v_1 + \sum_{j=2}^{k} c'_j a_j.$$
Multiplying both sides by $a_1$ and taking $g$ from both sides yields
$$g(u_1 a_1) + \sum_{j=2}^{k} g(c_j a_1 a_j) = g(v_1 a_1) + \sum_{j=2}^{k} g(c'_j a_1 a_j).$$
Thus, $g(u_1 a_1) = g(v_1 a_1)$.
For every $x = \sum a_i u_i \in S$ we define a function $f_1(x) = g(a_1 u_1)$. If $x \in S$ can be written $x = \sum a_i u_i$ and also $x = \sum a_i u'_i$ then $g(a_1 u_1) = g(a_1 u'_1)$. Moreover, if $x, z$ both are in $S$ such that $x \equiv z \pmod{D_1}$ then we have $f_1(x) = f_1(z)$. We finally observe that every residue class $\mod D_1$ contains elements in $S$, in fact already elements of the subset $a_1 u_1$ ($u_1 \ge 0$), because $\text{gcd}(a_1, D_1) = 1$. We may therefore extend the definition of $f_1(x)$ to all integers obtaining a function having the period $D_1$. Similarly, we define a function $f_i(x)$ ($i = 1, \dots, k$) over all integers, having the period $D_i$ with the property that $f_i(x) = g(a_i u_i)$ if $x = \sum a_i u_i \in S$.
And, in particular $f_i(0) = 0$. If $x = \sum a_i u_i \in S$ then the functional equation gives
$$g(x) = g(\sum a_i u_i) = \sum g(a_i u_i) = \sum f_i(x).$$
Hence, $g(x) = f_1(x) + \dots + f_k(x)$. We now use this to extend the definition of $g(x)$ to all integers $x$. Let us show that this implies $g(a_i u_i) = f_i(a_i u_i)$. Indeed, if $u_i \ge 0$ we have nothing to do. If $u_i < 0$ then we shall have $g(a_i u_i) = \sum f_i(a_i u_i) = f_i(a_i u_i)$. It follows that $g(x)$ satisfies the unrestricted equation
$$g(\sum a_i u_i) = \sum g(a_i u_i), \quad u_i \in \mathbb{Z}.$$
The converse is also easy. Indeed, the periodic function $f_i(x)$ depends on $D_i - 1$ arbitrary parameters and therefore the general solution depends on $1 + \sum (D_i - 1)$ arbitrary parameters. So, if all $D_i = 1$ the function is $f(x) = Cx$.
The least slope among the slopes of the sides of the polygonal graph of the function $f_i(x)(x \in \mathbb{Z})$ is given by $-m_i = \min_{x \in \mathbb{Z}} \Delta f_i(x)$, where $\Delta f_i(x) = f_i(x+1) - f_i(x)$. Evidently, $m_i \ge 0$. If we choose $C \ge \sum m_i$ then $f(x)$ is certainly non-decreasing since for all $x: \Delta f(x) = C + \sum \Delta f_i(x) \ge C - \sum m_i \ge 0$.
We then prove that the solution of the above functional equation is non-decreasing if and only if $\sum_{i=1}^k m_i \le C$. Indeed, let the minimum of $\Delta f_i(x)$ is reached at $x \equiv c_i \pmod{D_i}$ so that $\Delta f_i(c_i) = -m_i$ ($i = 1, \dots, k$). Since $D_i$ are pair-wise coprime. By the CRT the system $x \equiv c_i \pmod{D_1}$ has a solution $t$. Then, $0 \le \Delta f(t) = C + \sum \Delta f_i(t) = C - \sum_{i=1}^k m_i$. ■