HMMT question about monic quadratics

Question

This is from the HMMT 2016/2017 tournament: (The tournament is long over so none can "cheat" from this) Determine the largest integer n such that there exist monic quadratic polynomials $p_{1}(x), p_{2}(x),p_{3}(x)$ with integer coefficients so that for all integers $i \in [1, n]$ there exists some $j \in [1, 3]$ and $m \in \mathbb Z$ such that $p_{j}(m) = i$.

Answer 1

The construction for $n = 9$ can be achieved with the polynomials $x^{2} + x + 1, x^{2} + x + 2,$ and $x^{2} + 5$.

---

First we consider what kinds of polynomials we can have. Let $p(x) = (x + h)^{2} + k$. $h$ is either an integer or half an integer. Let $k = 0$. If $h$ is an integer then $p(x)$ hits the perfect squares $0, 1, 4, 9,$ etc. If $h$ is half an integer, then let $k = \frac{1}{4}$. Then $p(x)$ hits the product of two consecutive integers, i.e. $0, 2, 6, 12,$ etc.

---

Assume there is a construction for $n = 10$. In both of the cases above, the most a polynomial can hit out of $10$ is $4$, in the $0,1,4,9$ case. Thus $p_{1}$ must hit $1,2,5,10,$ and $p_{2}$ and $p_{3}$ hit $3$ integers each, out of $3, 4, 6, 7, 8, 9$. The only ways we can hit $3$ out of $7$ consecutive integers is with the sequences $0, 2, 6$ or $0,1,4$. The only way a $0,2,6$ works is if it hits $3, 5,$ and $9$, which doesn’t work since $5$ was hit by $p_{2}$. Otherwise, $p_{2}$ is $0, 1, 4,$ which doesn’t work as $p_{2}$ hits $3, 4,$ and $7$, and $p_{3}$ must hit $6, 8,$ and $9$, which is impossible. Thus no construction for $n = 10$ exists.