PMO Area Stage

Solution:

Let $S_{n}=\sum_{k=1}^{n} f(k)$. We want the value of $S_{2018}$.

Claim: $f(n)= \begin{cases}n & \text{ if } S_{n-1}<n \\ -n & \text{ if } S_{n-1} \geq n\end{cases}$

Proof: The inequality condition is $0 \leq S_{n-1}+f(n)<2 n$.

- If $n>S_{n-1}$, then $0 \leq S_{n-1}+f(n)<n+f(n)$ so $f(n)>-n$. Therefore, $f(n)=n$.
- If $n \leq S_{n-1}$, then $n+f(n) \leq S_{n-1}+f(n)<2 n$ so $f(n)<n$. Therefore, $f(n)=-n$.

Claim: If $S_{n}=0$, then

The pattern here: $S_{n+1}, S_{n+3}, S_{n+5}, \ldots$ are numbers decreasing by 1, while $S_{n+2}, S_{n+4}, S_{n+6}, \ldots$ are numbers increasing by 1.

Proof: $S_{n}=0<n$ so $f(n+1)=n+1$. Thus, $S_{n+1}=0+(n+1)=n+1$.

$S_{n+1}=n+1<n+2$ so $f(n+2)=n+2$. Thus, $S_{n+2}=n+1+(n+2)=2n+3$.

$S_{n+2}=2n+3>n+3$ so $f(n+3)=-n-3$. Thus, $S_{n+3}=2n+3+(-n-3)=n$.

We prove the claim by strong induction. Suppose the pattern holds for $S_{n+1}, S_{n+2}, \ldots, S_{n-1+2j}$.

Since $S_{n-1+2j}=S_{n+1+2(j-1)}=n+1-(j-1)=n+2-j<n+2j$, then $f(n+2j)=n+2j$ so $S_{n+2j}=(n+2-j)+(n+2j)=2n+2+j$.

On the other hand, since $S_{n+2j}=2n+2+j=(n+2j+1)+(n+1-j) \geq n+2j+1$, then $f(n+2j+1)=-(n+2j+1)$ so $S_{n+2j+1}=(2n+2+j)-(n+2j+1)=n+1-j$, which proves the claim.

Eventually, $S_{n+1}, S_{n+3}, \ldots, S_{n+2j+1}, \ldots$ will decrease to 0, when $j=n+1$. Thus, if $S_{n}=0$, it follows that the next 0 value is $S_{3(n+1)}$.

Therefore, $S_{3}=0$, $S_{3 \cdot 4}=S_{12}=0$, $S_{3 \cdot 13}=S_{39}=0$, $S_{3 \cdot 40}=S_{120}=0$, $S_{3 \cdot 121}=S_{363}=0$, $S_{3 \cdot 364}=S_{1092}=0$.

Since $2018=1092+2 \cdot 463$, then $S_{2018}=2 \cdot 1092+2+463=2649$.