$\newcommand{\rational}{\mathbb{Q}}$
I have met the following interesting problem:
Prove, given a positive integer $n \geq 12$, if an integer polynomial $f(x)$ of degree $n$ evaluates to $\pm 1$ at more than $[\frac{n}{2}] + 1$ distinct integers of $x$, then $f(x)$ is irreducible over $\rational$. Can the lower bound $12$ of the degree $n$ be further reduced?
My attempt: Assume the contrary, $f(x) = g(x)h(x)$, where $\deg(g(x)) < n, \deg(h(x)) < n$. Denote $[n/2] + 1$ by $m$, then either $\deg(g(x)) < m$ or $\deg(h(x)) < m$, say $g(x)$. Let $a_1, \ldots, a_m$ be $m$ distinct integers such that $f(a_i) = \pm 1, i = 1, \ldots, m$. Then $g(a_i) = \pm 1, i = 1, \ldots, m$. As $\deg(g(x)) < m$, this implies that there exists $1 \leq j < m$, such that $g(a_1) = \cdots = g(a_j) = 1$ while $g(a_{j + 1}) = \cdots = g(a_m) = -1$. Since $g$ is an integer polynomial and $a_1, \ldots, a_m$ are distinct, this requires $j \leq 3$ and $m - j \leq 3$, whence $m \leq 3 + j \leq 6$. Therefore $n \leq 11$. This contradicts with $n \geq 12$.
How about the second part of the problem? Does there exist an integer polynomial of degree less than $12$ with the stated property? I have difficulty to construct one.