Inspired by Steven Yuan

[This is not a complete solution.]

Most people make the mistake that since the polynomial looks like $f(x) = x^2 + 4$ , hence they think the minimum is $f(4) = 4^2 + 4 = 20$ . How do we know that there isn't a higher-degree polynomial which allows us to minimize $f(4)$ ?

Hint: The only polynomials with integer coefficients that satisfy $f(1) = 0$ are of the form $f(x) = g(x) \times (x-1)$ , where $g(x)$ is a polynomial with integer coefficients.

Hint: The only polynomials with integer coefficients that satisfy $f(1) = 0, f(2) = 0 , f(3) = 0$ are of the form $f(x) = g(x) \times (x-1)(x-2)(x-3)$ , where $g(x)$ is a polynomial with integer coefficients.

Hint: Hence classify all polynomials that satisfy the conditions of the problem.

Hint: Hence, determine the minimum possible positive value of $f(n)$ .

Is it taboo to write a solution to a problem that was inspired by a self-proposed problem? :P

Anyway, this problem can still be tackled with a number theoretic approach. Let $y = f(4).$ Since $f$ has integer coefficients, we know that $y$ is also an integer. Furthermore, we know that, for all integers $a, b,$ we have $a - b|f(a) - f(b).$ Substituting in $a = 4$ and $b = 1, 2, 3$ gives

$\begin{aligned} 3 &| \, y - 5 \\ 2 &| \, y - 8 \\ 1 &| \, y - 13, \\ \end{aligned}$

resulting in the system of congruences

$\begin{aligned} y &\equiv 5 \equiv 2 \! \! \! \! \pmod{3} \\ y &\equiv 8 \equiv 0 \! \! \! \! \pmod{2}. \end{aligned}$

We can immediately see that $y = \boxed{2}$ is the smallest possible positive value of $y$ that satisfies this system. Indeed, $f(x) = -3x^3 + 19x^2 - 33x + 22$ is a polynomial with integer coefficients such that $f(4) = 2$ is satisfied, along with the problem conditions.

---

I'll also present the algebraic method, which allows us to find a suitable polynomial directly. Notice that $f(x) = x^2 + 4$ holds for $x = 1, 2, 3.$ Therefore, we can factor $f(x)$ as

$f(x) = x^2 + 4 + g(x)(x - 1)(x - 2)(x - 3),$

for some polynomial $g(x)$ with integer coefficients. Plugging in $x = 4$ yields $f(4) = 20 + 6g(4).$ Since $f(4) \equiv 2 \! \pmod{6},$ we find again that $f(4) = \boxed{2}$ is our smallest positive value of $f(4).$ This can be achieved, for example, when $g(x) = -3,$ which yields the $f(x)$ we found in the previous solution.