ELMO 2013 Problem 6

Consider a function $f: \mathbb Z \to \mathbb Z$ such that for every integer $n \ge 0$ , there are at most $0.001n^2$ pairs of integers $(x,y)$ for which $f(x+y) \neq f(x)+f(y)$ and $\max\{ \lvert x \rvert, \lvert y \rvert \} \le n$ . Is it possible that for some integer $n \ge 0$ , there are more than $n$ integers $a$ such that $f(a) \neq a \cdot f(1)$ and $\lvert a \rvert \le n$ ?

Proposed by David Yang