To anticipate some comments that may arise: the Problem Selection Committee of BxMO was aware that this problem is rather similar to Problem 6 of IMO 1974, but decided that this was not an issue for this competition. (This problem was constructed by the PSC based on a lemma in the solution of a problem on the shortlist for the competition that was well liked by the PSC, but thought to be too hard for the competition.)

Without loss of generality, assume there were at least $\dfrac{d+1}{2}$ roots of $P(x)$ (otherwise take $-P(x)$). Also note $P(x)-1$ has at most $d$ roots, so there is at least one root to $P(x)=-1$. Define $Q(x):=P(x)-1$. If $d\geq 7$, we have that $P(x)$ has at least $4$ different roots, say $r_1,r_2,r_3,,r_4$. Then, we can write \[Q(x)=(x-r_1)(x-r_2)(x-r_3)(x-r_4)R(x)\]This has at least one nonzero root. However, we get that $x\neq r_1,r_2,r_3,r_4$, so thus we get that at least two of $x-r_1,x-r_2,x-r_3,x-r_4$ have absolute value greater than $1$. However, as $|R(x)|\geq 1$ (otherwise $Q(x)=0$), we must have $|Q(x)|\geq 4$. However, if $P(x)=-1$, $Q(x)=-2$, a contradiction. Thus, we must have $d\leq 6$. If $d\geq 4$, then there are at least $2$ different roots of $P(x)-1$, say $r_1,r_2,r_3$. Then, we can write \[P(x)-1=(x-r_1)(x-r_2)(x-r_3)R(x)\]This has at least one of $x-r_1,x-r_2,x-r_3$ with absolute value greater than $1$. However, as $|R(x)|\geq 1$, we must have $x-r_1,x-r_2,x-r_3=\{1,-1,2\},\{1,-1,-2\}$. Both of these can not simultaneously hold, so thus we have at most $1$ root, a contradiction. It suffices to check $d=1,2,3$. We shall provide a construction: \[P_3(x)=-x(x-2)(x-3)+1,m=0,1,2,3\]\[P_2(x)=x(x-3)+1,m=0,1,3\]\[P_1(x)=2x-1,m=0,1\]

For $d=1$, take $P=X$ for $m \in \{-1, 1 \}$ For $d=2$, take $P=X(X+1) - 1$ for $m \in \{-1, 0, 1 \}$ For $d=3$, take $P=X(X + 1)(X-2)+1$ for $m \in \{-1,0, 1, 2 \}$. Now suppose $d \geq 4$. Let $A=\{ a \in \mathbb{Z} ~| ~ P(a)=1\}$ and $B=\{ b \in \mathbb{Z} ~| ~ P(b)=-1\}$. Let $(a, b) \in A \times B$, then we have $a-b \mid P(a) - P(b)$, hence $b \in \{a-2, a-1, a+1, a+2 \}$, therefore $\# B \leq 4$. The same for $A$, we have $\# A \leq 4$. Therefore $d \leq 7$. Case 1: $A=\{ a\}$ Since $\#B \geq d + 1 - \#A \geq 4$, we must have $B=\{a-2, a-1, a+1, a+2\}$. So there exists $Q \in \mathbb{Z}[X]$ such that $P=-1+(X-a+2)(X-a+1)(X-a-1)(X-a-2)Q(X)$. Evaluate at $a$ to get $2=4Q(a)$ which is absurd. Case 2: $A=\{ a, b\}$ where $a < b$. Since $\#B \geq d + 1 - \#A \geq 3$, and $B \subseteq \{a-2, a-1, a+1, a+2\} \cap \{b-2, b-1, b+1, b+2\}$, then we must have $\{a-1, a+1, a+2\}=\{b-2, b-1, b+1\}$, which is absurd (it leads to $b=a+1=a+2$). Case 3: $A=\{ a, b, c\}$ where $a < b < c$. Since $\#B \geq d + 1 - \#A \geq 2$, and $B \subseteq \{a-2, a-1, a+1, a+2\} \cap \{b-2, b-1, b+1, b+2\} \cap \{c-2, c-1, c+1, c+2\}$, then we must have $\{a+1, a+2\}=\{b-1, b+1\}=\{c-2, c-1\}$, which is absurd (it leads to $b=a+2=a+1$ again). Case 4: $A=\{ a, b, c, e\}$ where $a < b < c < e$. Since $\#B \geq d + 1 - \#A \geq 1$, and $B \subseteq \{a-2, a-1, a+1, a+2\} \cap \{b-2, b-1, b+1, b+2\} \cap \{c-2, c-1, c+1, c+2\} \cap \{e-2, e-1, e+1, e+2\}$, then we must have $a+2=b+1=c-1=e-2$. So let $Q \in \mathbb{Z}[X]$ such that $P=1+(X-a)(X-a-1)(X-a-3)(X-a-4)Q(X)$ and evaluate at $a+2$ to get $2=4Q(a+2)$ which is absurd. Therefore, $d>3$ are not valid values.

For $d=1,2,3$ there is polynomial with degree $d$ which satisfies the problem condition.Indeed , for $d=1$ take $p(x)=x+1$.For $x=0$ and $-2$ the ondition holds. for $d=2$ take $p(x)=(x-1)(x-4)+1$.For $x=1,4,3$ the problem condition holds. for $d=3$ take $p(x)=(10-x)(12-x)(13-x)+1$.For $x=10,11,12,13$ the problem condition holds. Now we will prove that for $d\ge 4$ no other such polynomial exists. LEMMA: No polynomial belongs to $\mathbb{Z}[X]$ can take $+1,-1$ each at least once in 6 different integers. proof: FTSOC, Assume in $a<b<c<d<e<f$ $P\in\mathbb{Z}[X]$ takes $+1$ or $-1$ each at least once.Also assume $P(a)=1$.[Otherwise we will take $-P(x)$].As $f-a,e-a,d-a\ge 3$ and $x-a|P(x)-P(a)$ for all integer $x$ so in $d,e,f$ $P$ can take $-1$.So $P(d)=P(e)=P(f)=1$ Again $f-b,f-c\ge 3$.Working same way as above $P(b)=P(c)=1$.But then $P$ doesn't take $-1$ in any one of $6$ values.Contradiction.$\blacksquare$ From the above lemma it is clear that no polynomial with deg$\ge5$ gas the problem property. Now we will prove that no 4 degree polynomial satisfies problem condition. Suppose there is a 4 degree integer polynomial which can take $+1$ or $-1$ value in $a<b<c<d<e$ each at least once.Take $P(a)=+$.[Otherwise take $-P(x)$] As $e-a,d-a$ are at least 3 working like the lemma we have $P(e)=P(d)=1$.Again as $e-b\ge 3$ so $f(b)=1$.So we must have $P(c)=-1$ and $c-a=2,e-c=2$.So$a,b,c,d,e$ are consecutive integers. So $P(a)=P(a+1)=P(a+3)=P(a+4)=1$ and $P(a+2)=-1$.Easy to note that $P(x)=(x-a)(x-a-1)(x-a-3)(x-a-4)+1$.But then $P(a+2)$ is not equal to $-1$ in anyway.Contradiction.So no 4 degree polynomial of the given property exists.

Solution. This is equivalent to finding $d$ such that $\exists P \ \in \mathbb{Z}[X]$ with \[S(P) = \#_{\mathbb{Z}}(P-1) + \#_{\mathbb{Z}}(P+1) \geq d+1 \]where $\#_{\mathbb{Z}}(P)$ denotes the number of distinct integral roots of $P$. Claim $$d \leq 3$$Proof. We will prove $S(P) \leq 4$ \[ P(x) + 1 = Q(x) (x-\alpha_1)^{a_1}(x-\alpha_2)^{a_2}\cdots (x-\alpha_k)^{a_k} \]\[ P(x) - 1 = Q(x) (x-\alpha_1)^{a_1}(x-\alpha_2)^{a_2}\cdots (x-\alpha_k)^{a_k} - 2\]If $P(x_0)-1 = 0$ with $x_0 \in \mathbb{Z}$, \[ Q(x_0)(x_0 - \alpha_1)^{a_1}(x_0 - \alpha_2)^{a_2} \cdots (x_0 - \alpha_k)^{a_k} = 2 \]So, either $Q(x_0) = \pm 2, k \leq 2$ or $Q(x_0) = \pm 1, k \leq 3$, translating we get, Case 1: \[ \pm2 x^{a_1}(x+c)^{a_2} \]$S(P) \leq 3$ Case 2: \[ \pm 1 x^{a_1}(x+c_1)^{a_2}(x+c_2)^{a_3}\]Sorting $x,x+c_1,x+c_2$ and translating accordingly such that $x > x+c_1 > x+c_2$, but then $x = 2 \text{ or } 1$ which determines the root itself. Thus, $S(P) \leq 4$ $\square$ Construction: $d = 1: x$ $d = 2: 2x^2 -1$ $d = 3: -x(x-1)(x-3)-1$ $\square$

Does this work Claim : If $P(x)=Q(x)R(x)$, where $P,Q \in \mathbb{Z}[X]$ and $Q$ is monic, then $R \in \mathbb{Z}[X]$ In the long division process, keep decreasing the degree of $P(x)$ at each point. At each point we need to multiply $Q(x)$ by an integer to do so (since $Q$ is monic). Therefore, $R(x) \in \mathbb{Z}[x]$ We need to sum up the number of integer roots of $P(m)+1=0$ and $P(m)-1=0$. Define $Q(m)=P(m)+1$, so we need to find the number of $m$ satisfying $Q(m)=0,2$. Let $Q(m)=(x-a_1)^{b_1}(x-a_2)^{b_2} \dots (x-a_l)^{b_l} \times T(m)$. Note that $T(m) \in \mathbb{Z}[X]$ and all $a_i$ are distinct. If $l \geq 4$, then the absolute value of this quantity becomes at least $4$ for all integer $x$, which means that this polynomial doesn’t not satisfy the problem conditions. So $l \leq 3$. Case 1: $Q$ has 3 distinct integer roots We must be able to find $x$ such that $(x-\alpha)(x-\beta)(x-\gamma) \mid 2$ (Here $\alpha>\beta>\gamma$). The possible values for the factors are $-2,-1,1$ and $-1,1,2$. But only one of this is possible since in both these cases $\alpha-\beta$ is different. Therefore $4 \geq d+1 \implies 3 \geq d$. Case 2: $Q$ has $2$ distinct integer roots. We must be able to find $x$ such that $(x-\alpha)(x-\beta) \mid 2$ where $\alpha>\beta$. The possible values for the factors are $(1,2), (-1,2), (-2,1), (-2,-1), (-1,1), (-2,2)$ and we can find a max of $2$ pairs here which keep $\alpha-\beta$ fixed. Therefore $4 \geq d+1 \implies 3 \geq d$. Case 3: Only one integer root. This case gives $5 \geq d+1 \implies 4 \geq d$. $d=4$ fails because the only way this is possible is when $Q(x)$ has one integer root, so we must be able to find $4$ values of $x$ so that $Q(x)=2$. But then there exists $x$ satisfying $Q(x)-2=(x-a_1)^{b_1} \dots (x-a_4)^{b_4}R(x)=-2$ which is not possible since at least 4 distinct integers are being multiplied so the absolute value must be at least $4$. For $d=1, x$ works, for $d=2, x^2+3x+1$ works, and for $d=3, (x-1)(x-3)(x-4)-1$ works.

The answer is $d \leq 3$ only. Constructions are $P(x)=2x-1,2x(x-2)+1,x(x-1)(x-3)+1$. Now we prove that $d \geq 4$ fail. Evidently we want at least $d+1$ total integer roots of $P(x)-1$ and $P(x)+1$. WLOG let $P(x)+1$ have at least $\tfrac{d+1}{2}$ of these roots; by shifting vertically the problem is then equivalent to having at least $d+1$ total integer roots of $P(x)$ and $P(x)-2$, with at least $\tfrac{d+1}{2}$ total integer roots of $P(x)$. Since $d \geq 4$, it follows that $P(x)$ has at least $3$ integer roots. First suppose that $P(x)-2$ has at least $2$ integer roots; note that $P(x)$ still has at least $3$ integer roots, so we can write $$P(x)=(x-a)(x-b)(x-c)Q(x)$$for some nonzero polynomial $Q$ and distinct integers $a,b,c$. But if $P(x)=2$, then we require $\{x-a,x-b,x-c\}=\{2,1,-1\},\{1,-1,-2\}$, since $a,b,c$ are distinct (so, for instance, we cannot have $x-a=x-b=1$ and $x-c=2$). If we WLOG suppose $a<b<c$, then if $\{x-a,x-b,x-c\}=\{2,1,-1\}$, then $b=a-1$ and $c=a-3$. On the other hand, if $\{x-a,x-b,x-c\}=\{1,-1,-2\}$, then $b=a-2$ and $c=a-3$, so these equivalences cannot both be true for some value of $x$, given a fixed choice of $(a,b,c)$. Since every equivalence yields exactly one value of $x$, it follows that $P(x)-2$ has at most one root in this case, which is a contradiction. If $P(x)-2$ has exactly $1$ integer root, then $P(x)$ must have at least $4$ integer roots. Again, we can write $$P(x)=(x-a)(x-b)(x-c)(x-d)Q(x)$$for some integers $a<b<c<d$. But then for $x$ to be a root of $P(x)-2$, we need $x-a,x-b,x-c,x-d \in \{1,-1,2,-2\}$, so by Pigeonhole $\{x-a,x-b,x-c,x-d\}=\{1,-1,2,-2\}$, but then $4 \mid P(x)$. Thus $P(x)-2$ has no roots, which is a contradiction. If $P(x)-2$ has no integer roots, then all $d+1$ roots must belong to $P(x)$. However, $P(x)$ has degree exactly $d$, so this is absurd—the only polynomial of degree at most $d$ which has at least $d+1$ roots is the zero polynomial, which clearly cannot have degree $d$. Thus $d \geq 4$ all fail, so we're done. $\blacksquare$

This was a pretty instructive and nice problem for someone like me who hasn't ever solved any poly problem before. The values of $d$ that work are $d=1,2,3$. For the constructions, we have the following polynomials, For $d=1$, $P(x)=x$ works with $x=+1, -1$. For $d=2$, $P(x)=x^2-3x+1$ works with $x=0,+1,+2$. For $d=3$, $P(x)=x^3-2x^2-x+1$ works with $x=-1,0,+1,+2$. Now we prove that $d\ge 4$ don't work. Firstly, note that $x-y\mid P(x)-P(y)\equiv 2$ which gives $x\in\left\{y+2,y+1,y-1,y-2\right\}$. Let $x_i$ denote the values for which $P(x_i)=-1$ and $y_i$ be the ones for which $P(y_i)=+1$ for the respective polynomial $P(x)$. Moreover, WLOG assume $x_i>x_j$ and $y_i>y_j$ for $i>j$. Firstly, note that if all the values of $P(m)$ turn out to be of the same sign, then the polynomial simply becomes a constant which is a contradiction. So each of the sets of $\left\{x_i\right\}$ and $\left\{y_i\right\}$ are non-empty. Now for $d\ge 8$, by PHP we get that there are at least $5$ elements in one of the sets, but we also found out earlier that the possible values for $x_i$ are $\left\{y_i+2,y_i+1,y_i-1,y_i-2\right\}$, which are a total of $4$ values. So by PHP on $5$ elements and $4$ possible boxes, we get that two values must be the same but this is a contradiction as it is told that the values are distinct. Now from our idea above, we have that no box must have $\ge 5$ elements in it. Let the tuple $(\bullet,\bullet)$ denote the number of elements of the set $\left\{x_i\right\}$ and $\left\{y_i\right\}$ respectively. So for $d=7$, we get that the only working tuple is $(4,4)$. But this is a contradiction as if we pick $y_i$ and $y_j$ from the set, then the possible values of the set of $x$ is $\left\{x_i+2,x_i+1,x_i-1,x_i-2\right\}$. But since this has exactly $4$ elements, the equality of the condition holds and these are our exact elements. But doing the same for $y_j$ we get that their maximum values are equal which forces $y_i=y_j$ a contradiction. Similarly, for $d=6$ we get the only working tuple is $(4,3)$ which again forces contradiction. For $d=5$, some case bash on the values of $x_i$ gives a similar contradiction. For $d=4$, a similar bash gives that the tuple $(3,2)$ does not work, and moreover, the tuple $(4,1)$ generates a polynomial with rational coefficients which is a contradiction and we are done.

Found this very straightforward. The answer is $d \leq 3$. Construction: $P(x) = 2x-1$, $P(x) = 2x^2-4x+1$, $P(x) = (x-1)(x-3)(x-4) - 1$ respectively. Bound: For some $k \leq d$, $P(x)$ is of the form $1+R(x)(x-a_1)(x-a_2)\cdots (x-a_k)$. In particular, $$R(x)(x-a_1)(x-a_2)\cdots (x-a_k) = -2$$for $d+1-k$ values of $x$. Assume $d \geq 4$, so we can set WLOG $k \geq 3$. We have essentially two cases: First Case: If there are exactly $k = 3$ values, then we have $d = 4$. Then $$\{x-a_1, x-a_2, x-a_3, R(x)\} = \{\pm 1, \mp 1, \pm 2, \pm 1\}$$for both values of $x$. But obviously by looking at the first three terms, this implies $\{a_1, a_2, a_3\} =\{k - 1, k + 1, k - 2\}$ for some $k$, and thus we cannot have two distinct values of $x$ work. Second Case: If there are $k \geq 4$ values, then note that there do not exist four distinct integers $x-a_1, \dots, x-a_4$ multiplying to $-2$, which is a contradiction.

For $d=0$ take the constant polynomial $P_0(x)=1$. For $d=1$ take the polynomial $P_1(x)=x$ then $|P_1(1)|=|P_1(-1)|=1$. For $d=2$ take the polynomial $P_2(x)=x(x+1)-1$ then $|P_2(1)|=|P_2(0)|=|P_2(-1)|=1$. For $d=3$ take the polynomial $P_3(x)=x(x+1)(x-2)+1$ then $|P_3(1)|=|P_3(-1)|=|P_3(0)|=|P_3(2)|=1$. Let $d\geq 4$. Suppose that there is a polynomial $P_d$ that satisfies $|P_d(x)|=1$ for $x=x_1,x_2,\dots,x_{d+1}$. Suppose that there are at least two such that $P_d$ is $1$ and at least two such that it is $-1$. Let's say, for convenience, $$P_d(x_1)=P_d(x_2)=1, \quad P_d(x_3)=P_d(x_4)=-1.$$Let's assume wlog that $P_d(x_5)=-1$. Notice that $$x_1-x_3\mid P_d(x_1)-P_d(x_3)=2$$and other similar relations. So we must have $$\{x_1-x_3,x_1-x_4,x_1-x_5,x_2-x_3,x_2-x_4,x_2-x_5\}=\{2,1,-1,-2\}.$$If we assume (wlog) that $x_1>x_2$ and $x_3<x_4<x_5$ then we must have $$x_1-x_3=2, x_1-x_4=1, x_1-x_5=-1, x_2-x_3=1, x_2-x_4=-1, x_2-x_5=-2.$$However note that $$2=x_1-x_4+x_2-x_3=(x_1-x_3)+(x_2-x_4)=2-1=1,$$a contradiction. This proves that $P_d$ can be $-1$ for at most one number, and rest must be $+1$ and vice versa. Clearly $P_d$ can't be $1$ (or resp $-1$) for all of them, since it is a non-constant polynomial. So wlog $P_d(x_1)=-1$ and $P_d(x_2)=P_d(x_3)=\dots=P(x_{d+1})=1$. It follows that $$P_d(x)=1+(x-x_2)\cdots(x-x_{d+1})$$for all $x$. So putting $x=x_1$ we get $$(x_1-x_2)(x_1-x_3)\cdots(x_1-x_{d+1})=-2.$$However this forces some of the factors to be equal to $1$ (or to $-1$), which implies that some of the $x_i$s are equal, a contradiction. This proves that $P_d$ cannot exist for $d\geq 4$.

We claim $d=1,2,3$. Let $m$ be the minimum for which $|P(m)|=1$, and WLOG $P(m)=1$. If $P(m+k)=-1$ then $k\mid P(m)-P(m+k)=2$ so $k\le 2$. Then if $P(m+\ell)=1$ we have $\ell-k\mid P(m+\ell)-P(m+k)=2$ so $\ell\le 4$, and if $P(m+\ell)=-1$ then $\ell\le 2$. Clearly we cannot have $d+1$ solutions to $P(x)=1$ or $-1$, so we have at most five solutions $m,m+1,m+2,m+3,m+4$ so $d\le 4$. When $d=4$ we can check $P(m)=1,P(m+2)=-1,P(m+4)=1$ imply $P(m+1)=P(m+3)=1$ so $P(x)-1=a(x-m)(x-m-1)(x-m-3)(x-m-4)$ and setting $x=m+2$ implies $a=-\tfrac12$ contradicting that it has integer coefficients. For $d=1,2,3$ take $P(x)=x,x^2-x-1,x^3-x^2-2x+1$.

The key idea is to use the lemma $a-b \mid P(a) - P(b)$ to analyse the distances between values $a$ and $b$ for which $P(a) = 1, P(b) = -1$, and thus get $d \le 4$. $d = 1, 2, 3$ can be constructed but the unique poly (upto shifting) for $d = 4$ doesn't have integer coefficients, yielding the solution set as $d \in \{1, 2, 3\}$.