TSTST 2016 Problem 3

Decide whether or not there exists a nonconstant polynomial $Q(x)$ with integer coefficients with the following property: for every positive integer $n>2$, the numbers $$Q(0), Q(1), Q(2), \ldots, Q(n-1)$$ produce at most $0.499 n$ distinct residues when taken modulo $n$.