1974 IMO Problems/Problem 6

Problem

Let $P$ be a non-constant polynomial with integer coefficients. If $n(P)$ is the number of distinct integers $k$ such that $(P(k))^2=1,$ prove that $n(P)-\deg(P)\le2,$ where $\deg(P)$ denotes the degree of the polynomial $P.$

Solution

Lemma: Let $P(x)$ be a polynomial with integer coefficients which is not constant. Then if $P(x)$ obtains $1$ (or $-1$ ) as its values for at least four times then $P(x)\neq -1$ ( or $P(x)\neq 1$ ) for all $x$ . Proof. Assume that $P(a)=P(b)=P(c)=P(d)=1$ for $a,b,c,d$ distince. Then if there's $u$ which $P(u)=-1$ then $2=P(a)-P(u)=...$ so $P(x)-P(u)-2=(x-a)(x-b)(x-c)(x-d)Q(x)$ where $Q(x)$ is a polynomial with the integer coefficients! So $-2=(u-a)(u-b)(u-c)(u-d)Q(u)$ which is impossible cause $-2$ can not presents as product of more than three distince numbers! This proved the lemma!

Back to our problem: For convinet put $m=n(P)$ and $n=\deg P$ . Firstly if $n\leq 2$ then $m-n\leq2$ . Assume $n\geq3$ . If equation $P(x)=1$ with more than three integer points (ie.. at least $4$ ) then equation $(P(x))^2=1$ implies $P(x)=1$ so $m\leq n$ , ie... $m-n\leq 0\leq2$ . The same case for equation $P(x)=-1$ . So $m\leq 6$ . If $n\geq4$ then $m-n\leq 6-n\leq 2$ . Now assume that $n=3$ . In this case if $m\leq 5$ then $m-n\leq 2$ .

So let us show that $m<6$ . In fact if $m=6$ then $P(x)-1=0$ has three integers distince roots, and the same for $P(x)+1=0$ . So $P(x)-1=k_1(x-a_1)(x-a_2)(x-a_3)$ and $P(x)+1=k_2(x-b_1)(x-b_2)(x-b_3)$ where $a_i$ distince and $b_j$ distince and all with $k_1,k_2$ are integers! Then $k_2(x-b_1)(x-b_2)(x-b_3)-k_1(x-a_1)(x-a_2)(x-a_3)=2$ for all $x$ . So $k_1=k_2=k$ . Finally, we have $2=k(a_i-b_1)(a_i-b_2)(a_i-b_3)$ for $i=1,2,3$ and because that $\pm1$ can not presents as products of three distince numbers so $k=\pm1$ , we may assume $k=1$ . Because $2=(-2)\cdot 1\cdot -1$ so $\{-2,1,-1\}=\{a_i-b_1,a_i-b_2,a_i-b_3\}$ This means $3a_i-(b_1+b_2+b_3)=-2+1-1=-2$ . So we must have $3a_1=3a_2=3a_3$ which follows $a_1=a_2=a_3$ , which contracts!. So $m\leq 5$ and we're done.

The above solution was posted and copyrighted by pluricomplex.

Remarks (added by pf02, October 2025)

$\mathbf{1.}$ The solution above is written very sloppily and badly, it could use substantial editing. However, the proof is understandable and correct, and I will refrain from rewriting it.

It is interesting to note that it actually proves substantially more than the problem asked. It proves the following two statements:

$\mathbf{a.}$ If one of the equations $P(x) - 1 = 0$ and $P(x) + 1 = 0$ has $\ge 4$ integer, distinct solutions, then the other has no integer solutions.

$\mathbf{b.}$ If both equations $P(x) - 1 = 0$ and $P(x) + 1 = 0$ have integer solutions then $n(P) \le 5$ .

The statement of the original problem is a trivial consequence of these statements (as I will show later).

$\mathbf{2.}$ This problem is in fact very easy. It is made difficult artificially, by hiding the essence of the description of the distinct, integer solutions of $P(x) - 1 = 0$ and $P(x) + 1 = 0$ . The essence is hidden behind a more general sounding (in some sense artificial) statement. Had it been formulated to express the essence of the description of the distinct, integer roots of $P(x) - 1 = 0$ and $P(x) + 1 = 0$ , the problem would have been much less intimidating, and much easier, because the facts would have pointed towards a solution.

Here is a reformulation the problem:

$\mathbf{Problem\ 2}$ Let $P(x)$ be a polynomial with integer coefficients of degree $d \ge 3$ . Let $m_1 =$ the number of distinct integer roots of $P(x) - 1 = 0$ , and $m_2 =$ the number of distinct integer roots of $P(x) + 1 = 0$ . If both $m_1 \ge 1, m_2 \ge 1$ then $m = m_1 + m_2 \le 5$ .

$\mathbf{Additional\ challenges}$

$\mathbf{a.}$ With the notation of Problem 2, assume we have a non-constant polynomial $P(x)$ with constant coefficients, and assume $m_1 \ge 1, m_2 \ge 1$ . Prove the stronger bound $m = m_1 + m_2 \le 4$ .

$\mathbf{b.}$ If $d = 2$ , give an example of $P(x)$ for which there are $4$ distinct integer roots of $P(x) - 1 = 0$ and $P(x) + 1 = 0$ .

$\mathbf{c.}$ If $d = 3$ , give an example of $P(x)$ for which there are $3$ distinct integer roots of $P(x) - 1 = 0$ and one root of $P(x) + 1 = 0$ .

$\mathbf{d.}$ If $d = 3$ show that it is impossible to have $m_1 = 2$ and $m_2 = 2$ .

$\mathbf{3.}$ Below I will prove Problem 2 (from which the.statement of the original problem follows trivially), as well as the additional challenges.

There will be some overlap of ideas with the first solution, but for the sake of making the solution self contained, I will fill in all the details.

Solution 2

Let $M_1 = \{a_1 < \dots < a_{m_1}\}$ be the integer, distinct solutions of $P(x) - 1 = 0$ , and let $M_2 = \{b_1 < \dots < b_{m_2}\}$ be the integer, distinct solutions of $P(x) + 1 = 0$ . Denote $M = \{s_1 < \dots < s_m\}$ the union $M_1 \cup M_2$ arranged in increasing order. Thus each $s_i$ could be an element $a_j \in M_1$ or an element $b_k \in M_2$ . We will just look at the sequence $M$ as a sequence of $a$ 's and $b$ 's.

Let $a$ satisfy $P(a) - 1 = 0$ and $b$ satisfy $P(b) + 1 = 0$ . Then $a - b \in \{-2, -1, 1, 2\}$ , in other words $|a - b| = 1$ or $|a - b| = 2$ . Indeed, $P(a) - P(b) = (a - b) Q$ for some integer $Q$ . From $P(a) - P(b) = 2$ it follows $(a - b) Q = 2$ , so $(a - b)$ must be a divisor of $2$ . We paraphrase this by saying that a solution of $P(x) - 1 = 0$ and a solution of $P(x) + 1 = 0$ are at distance at most $2$ .

In terms of looking at $M$ as a sequence of $a$ 's and $b$ 's, given that all the $s_i$ 's are distinct, this tells us that the distance in the counting (or indexing) in the sequence, any $b$ is at most two away from any $a$ . In other words, if we have an $a$ , then at most two entries to the right and two entries to the left are $b$ 's, and similarly, if we have a $b$ , then at most two entries to the right and two entries to the left are $a$ 's.

It follows that $M$ can not have $6$ (or more) elements.

Indeed, $m$ has $6$ elements and assume $s_1$ is an $a$ . Then $s_4, s_5, s_6$ must be $a$ 's. Since $s_6$ is an $a$ , $s_2, s_3$ must be $a$ 's. It follows that all $s_i$ 's are $a$ 's, which is a contradiction since we assumed we have at least one $b$ .

$\mathbf{Note}$ This argument does not exclude $m = 5$ . For example, we could have a sequence $M = \{a, a, b, a, a\}$ .

This finishes the proof of problem 2.

$\mathbf{Note}$ The statement of the original problem follows trivially from Problem 2. Indeed, if only one of $P(x) - 1 = 0$ and $P(x) + 1 = 0$ has integer roots, then $n(P) \le d < d + 2$ . If the degree $d$ of $P(x)$ is $1$ or $2$ , then $n(P) \le 2, 4$ respectively, which is less than $d + 2$ . If the degree $d \ge 3$ then $n(P) = m \le 5 \le d + 2$ .

$\mathbf{Proof\ of\ the\ additional\ challenges}$

$\mathbf{a.}$ Let us prove the stronger bound $m = m_1 + m_2 \le 4$ .

Assume that $m = m_1 + m_2 = 5$ . Then we have that $m_1, m_2$ are $4$ and $1$ (in some order), or $m_1, m_2$ are $3$ and $2$ (in some order).

Assume $m_1 = 4, m_2 = 1$ . This is impossible because of the argument from the first solution. (Repeat the argument for the sake of completeness: Assume $P(a_1) = P(a_2) = P(a_3) = P(a_4) = 1$ and $P(b_1) = -1$ . Then $P(x) = (x - a_1)(x - a_2)(x - a_3)(x - a_4) Q(x) + 1$ with $Q(x)$ having integer coefficients. Substituting $x = b_1$ we have $(b_1 - a_1)(b_1 - a_2)(b_1 - a_3)(b_1 - a_4) Q(b_1) = -2$ . It follows that the values of the four factors $(b_1 - a_i)$ must be in $\{-2, -1, 1, 2\}$ . Since they are distinct, they must be exactly these four values. Then $(b_1 - a_1)(b_1 - a_2)(b_1 - a_3)(b_1 - a_4) Q(b_1)$ will be a multiple of 4, and it can not equal $-2$ .)

Now assume $m_1 = 3, m_2 = 2$ . Then $P(x) = (x - a_1)(x - a_2)(x - a_3) Q_1(x) + 1$ and $P(x) = (x - b_1)(x - b_2) Q_2(x) + 1$ for some $a_1, a_2, a_3, b_1, b_2$ (all distinct), and $Q_1(x), Q_2(x)$ some polynomials with integer coefficients. Then $(x - a_1)(x - a_2)(x - a_3) Q_1(x) - (x - b_1)(x - b_2) Q_2(x) = -2$ .

Substituting $x = b_1, b_2$ we have

$(b_1 - a_1)(b_1 - a_2)(b_1 - a_3) Q_1(b_1) = -2$

$(b_2 - a_1)(b_2 - a_2)(b_2 - a_3) Q_1(b_1) = -2$

Then each $(b_j - a_i)$ must equal one of $-2, -1, 1, 2$ . We now need to make a very careful analysis of all the cases when $(b_j - a_i)$ take all the possible values. Approached with brute force, there would be $4^6 = 4096$ cases, but we can reduce this enormously.

Think of listing the $6$ entries, in two groups of $3$

$(b_1 - a_1)\ \ (b_1 - a_2)\ \ (b_1 - a_3)\ \ \ \ (b_2 - a_1)\ \ (b_2 - a_2)\ \ (b_2 - a_3)$

The values of the entries in the first group of $3$ have to be distinct, and the values of the entries in the second group of $3$ have to be distinct.

The first entries in the two groups have to be distinct, and the same goes for the second and third entries.

We must not have a $2$ and $-2$ within the same group of $3$ entries.

Two triplets of values in a group which differ by a sign are equivalent (e.g. $1, -1, 2$ and $-1, 1, -2$ ).

The idea of the proof is to list all the relevant choices for $(b_j - a_i)$ , and see that the choice of values leads to a contradiction. The final check will be to verify whether $(b_1 - a_1) - (b_1 - a_2) = (b_2 - a_1) - (b_2 - a_2)$ and $(b_1 - a_2) - (b_1 - a_3) = (b_2 - a_2) - (b_2 - a_3)$ .

It will turn out that it is impossible to choose values for the two groups of $6$ entries so that all the constraints and the two equalities above are satisfied.

I will not show here all the cases; instead, I will show some very typical examples. It is not difficult for the reader to verify all the cases, or to write a little computer program which verifies all the cases.

[TO BE CONTINUED]

The original thread for this problem can be found here: [1]

1974 IMO (Problems) • Resources
Preceded by Problem 5	1 • 2 • 3 • 4 • 5 • 6	Followed by Last Question
All IMO Problems and Solutions

Page

Toolbox

Search

1974 IMO Problems/Problem 6

Contents

Problem

Solution

Remarks (added by pf02, October 2025)

Solution 2

See Also