Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1974 IMO Problems/Problem 6"
Line 25: Line 25:
 
==Remarks (added by pf02, October 2025)==
 
==Remarks (added by pf02, October 2025)==
  
−
<math>\mathbf{1.}</math>  The solution above is written very badly, it could
+
<math>\mathbf{1.}</math>  The solution above is written very sloppily and
−
use substantial editing.  Also, it is incomplete.  Indeed, the
+
badly, it could use substantial editing.  However, the proof is
−
statement "So <math>m \le 6</math>" is not put in a proper context, and it
+
understandable, and I will refrain from
−
is not properly justified.
+
rewriting it.
  
−
However, the proof is understandable, and the gap can be filled
+
It is interesting to note that it actually proves substantially
−
in by a diligent reader.
+
more than the problem asked.  It proves the following two
 +
statements:
  
−
It is interesting to note that (if we accept it as a proof) it
+
<math>\mathbf{a.}</math>  If one of the equations <math>P(x) - 1 = 0</math> and
−
actually proves substantially more than the problem asked.  It
 
−
proves the following two statements:
 
−
 
 
−
<math>\mathbf{a:}</math>  If one of the equations <math>P(x) - 1 = 0</math> and
 
 
<math>P(x) + 1 = 0</math> has <math>\ge 4</math> integer, distinct solutions, then
 
<math>P(x) + 1 = 0</math> has <math>\ge 4</math> integer, distinct solutions, then
 
the other has no integer solutions.
 
the other has no integer solutions.
  
−
<math>\mathbf{b:}</math>  If both equations <math>P(x) - 1 = 0</math> and
+
<math>\mathbf{b.}</math>  If both equations <math>P(x) - 1 = 0</math> and
 
<math>P(x) + 1 = 0</math> have integer solutions then <math>n(P) \le 5</math>.
 
<math>P(x) + 1 = 0</math> have integer solutions then <math>n(P) \le 5</math>.
  
Line 47: Line 44:
 
of these statements.
 
of these statements.
  
−
<math>\mathbf{2.}</math>  This problem is very easy.  It is made difficult
+
<math>\mathbf{2.}</math>  This problem is in fact very easy.  It is made
−
artificially by hiding the essence of the description of the
+
difficult artificially by hiding the essence of the description
−
distinct, integer solutions of <math>P(x) - 1 = 0</math> and <math>P(x) + 1 = 0</math>
+
of the distinct, integer solutions of <math>P(x) - 1 = 0</math> and
−
behind a more general sounding statement.  Had it been formulated
+
<math>P(x) + 1 = 0</math> behind a more general sounding statement.  Had
−
to state the essence, it would have been much less intimidating,
+
it been formulated to state the essence, it would have been
−
and easier, because the essence would have pointed towards a
+
much less intimidating, and easier, because the essence would
−
solution.
+
have pointed towards a solution.
  
 
Here is a reformulation the problem:
 
Here is a reformulation the problem:
  
−
<math>\mathbf{Problem/ 2:}</math>  Let <math>P(x)</math> be a polynomial of degree <math>d \ge 3</math>.
+
<math>\mathbf{Problem\ 2}</math>  Let <math>P(x)</math> be a polynomial of degree <math>d \ge 3</math>.
 
Let <math>m_1 =</math> the number of distinct integer roots of <math>P(x) - 1 = 0</math>,
 
Let <math>m_1 =</math> the number of distinct integer roots of <math>P(x) - 1 = 0</math>,
 
and <math>m_2 =</math> the number of distinct integer roots of <math>P(x) + 1 = 0</math>.
 
and <math>m_2 =</math> the number of distinct integer roots of <math>P(x) + 1 = 0</math>.
 
If both <math>m_1 \ge 1, m_2 \ge 1</math> then <math>m = m_1 + m_2 \le 5</math>.
 
If both <math>m_1 \ge 1, m_2 \ge 1</math> then <math>m = m_1 + m_2 \le 5</math>.
  
−
<math>\mathbf{Additional\ challenges:}</math>
+
<math>\mathbf{Additional\ challenges}</math>
  
−
<math>\mathbf{a:}</math>  With the notation of Problem 2, we have the stronger
+
<math>\mathbf{a.}</math>  With the notation of Problem 2, we have the stronger
 
bound <math>m = m_1 + m_2 \le 4</math>.
 
bound <math>m = m_1 + m_2 \le 4</math>.
  
−
<math>\mathbf{b:}</math>  If <math>d = 2</math>, find <math>P(x)</math> so that there are <math>4</math> distinct
+
<math>\mathbf{b.}</math>  If <math>d = 2</math>, find <math>P(x)</math> so that there are <math>4</math> distinct
 
integer roots of <math>P(x) - 1 = 0</math> and <math>P(x) + 1 = 0</math>.
 
integer roots of <math>P(x) - 1 = 0</math> and <math>P(x) + 1 = 0</math>.
  
−
<math>\mathbf{c:}</math>  If <math>d \ge 3</math> and both <math>m_1 \ge 1, m_2 \ge 1</math>, then one
+
<math>\mathbf{c.}</math>  If <math>d \ge 3</math> and both <math>m_1 \ge 1, m_2 \ge 1</math>, then we
−
of <math>m_1, m_2</math> equals <math>1</math> and the other equals <math>2</math> or <math>3</math> (in other
+
can not have <math>m_1 \ge 2</math> and <math>m_2 \ge 2.</math>
−
words, we can not have <math>m_1 = m_2 = 2).</math>
 
  
−
<math>\mathbf{3.}</math>  Below I will prove this Problem 2 (from which the
+
<math>\mathbf{3.}</math>  Below I will prove Problem 2 (from which the.statement
−
statement of the original problem follows trivially), as well as
+
of the original problem follows trivially), as well as.the additional
−
the additional challenges.
+
challenges.
  
 
There will be some overlap of ideas with the first solution, but for
 
There will be some overlap of ideas with the first solution, but for
Line 84: Line 80:
  
 
==Solution 2==
 
==Solution 2==
 +
 +
Let <math>M_1 = \{a_1 < \dots < a_{m_1}\}</math> be the integer, distinct solutions
 +
of <math>P(x) - 1 = 0</math>, and let <math>M_2 = \{b_1 < \dots < b_{m_2}\}</math> be the
 +
integer, distinct solutions of <math>P(x) + 1 = 0</math>.  Denote <math>\delta = \pm 1</math>,
 +
in the sense that <math>\delta</math> can stand for either of the two values.
 +
Denote <math>M = \{s_1 < \dots < s_m\}</math> the union <math>M_1 \cup M_2</math> arranged
 +
in increasing order.  Thus each <math>s_i</math> could be an element <math>a_j \in M_1</math>
 +
or an element <math>b_k \in M_2</math>.
 +
 +
Let <math>a</math> satisfy <math>P(a) - 1 = 0</math> and <math>b</math> satisfy <math>P(b) + 1 = 0</math>.  Then
 +
<math>a - b \in \{-2, -1, 1, 2\}</math>, in other words <math>|a - b| = 1</math> or <math>|a - b| = 2</math>.
 +
Indeed, <math>P(a) - P(b) = (a - b) Q</math> for some integer <math>Q</math>.  From
 +
<math>P(a) - P(b) = 2</math> it follows <math>(a - b) Q = 2</math>, so <math>(a - b)</math> must be a divisor
 +
of <math>2</math>.  We paraphrase this by saying that a solution of <math>P(x) - 1 = 0</math>
 +
and a solution of <math>P(x) + 1 = 0</math> are at distance at most <math>2</math>.
 +
 +
Now let us look at the solutions <math>\{s_i\}</math> and the values
 +
<math>\{\delta_i = P(s_i)\}</math>:
 +
 +
<math>s_1      <        s_2    <      \dots <      s_{m-1}    <      s_m</math>
 +
 +
<math>\delta_1\ \ \ \ \ \delta_2\ \ \ \ \dots\ \ \ \ \delta_{m-1}\ \ \ \ \delta_m</math>
 +
 +
Note that if for an <math>i</math> the root <math>s_i = a_j</math> for some <math>j</math> then at most two
 +
<math>s_{i'}</math> to the right and at most two to the left can be <math>b_k</math> for some <math>k</math>
 +
(otherwise the distance from <math>a_j = s_i</math> to them would be <math>> 2</math>).  In terms
 +
of <math>\{\delta_i\}</math> this says that if we have a <math>+1</math> in the sequence, at most
 +
two to the right and two to the left can be <math>-1</math>.  Similarly, if we have a
 +
<math>-1</math>, at most two to the right and two to the left can be <math>+1</math>.
 +
 +
This proves that if the sequence <math>\{\delta_i\}</math> contains both <math>+1</math> and <math>-1</math>,
 +
its length can be at most <math>5</math>.  Indeed, if it were of length <math>\ge 6</math>, it
 +
would contain a <math>+1</math> and a <math>-1</math> at distance <math>\ge 2</math>.
 +
 +
This finishes the proof of problem 2.
 +
 +
<math>\mathbf{Note}</math>  Just in case this is not clear enough: assume we have
 +
a sequence <math>\{\delta_1, \delta_2, \delta_3, \delta_4, \delta_5, \delta_6\}.</math>
 +
Assume <math>\delta_1 = +1</math>.  Since we must have at least one <math>-1</math>, take it to
 +
be as far as possible, say <math>\delta_3 = -1</math>.  Then <math>\delta_6 = -1</math> because
 +
otherwise, if <math>\delta_6 = +1</math>, it would be more than <math>2</math> away from
 +
<math>\delta_3 = -1</math>.  But then <math>\delta_6 = -1</math> is more than <math>2</math> away from
 +
<math>\delta_1 = +1</math>.
 +
 +
If we took <math>\delta_2 = -1</math>, a similar argument would show that we can not
 +
have a sequence of <math>6</math> values of <math>+1</math> and <math>-1</math> such that there are no two
 +
entries with opposing sign more that <math>2</math> away from each other.
 +
 +
<math>\mathbf{Note}</math>  The statement of the original problem follows trivially
 +
from Problem 2.  Indeed, if only one of <math>P(x) - 1 = 0</math> and <math>P(x) + 1 = 0</math>
 +
has integer roots, then <math>n(P) \le d < d + 2</math>.  If the degree <math>d</math> of <math>P(x)</math>
 +
is <math>1</math> or <math>2</math>, then <math>n(P) \le 2, 4</math> respectively, which is less than <math>d + 2</math>.
 +
If the degree <math>d \ge 3</math> then <math>n(P) = m \le 5 \le d + 2</math>.
 +
 +
<math>\mathbf{Proof\ of\ the\ additional\ challenges}</math>
 +
 +
<math>\mathbf{a.}</math>  We have the stronger bound <math>m = m_1 + m_2 \le 4</math>.
 +
 +
Indeed, let us look at the sequence
 +
<math>\{\delta_1, \delta_2, \delta_3, \delta_4, \delta_5\}.</math>
 +
We can assume <math>\delta_1 = +1</math>.  If <math>\delta_2 = -1</math>, then
 +
<math>\delta_5</math> must be <math>-1</math> (otherwise <math>\delta_5 = +1</math> would
 +
be at distance <math>> 2</math> from <math>\delta_2 = -1</math>.  But then
 +
<math>\delta_5 = -1</math> is at distance <math>> 2</math> from <math>\delta_1 = +1</math>.
 +
 +
(To make this more intuitive, I just proved that we can not
 +
have the sequence <math>\{+1, -1, +1, +1, -1\}</math>.)
 +
 +
However, in principle, we could have the sequences
 +
<math>\{+1, +1, -1, +1, +1\}</math> and <math>\{+1, -1, +1, -1, +1\}.</math>
 +
 +
The first one, <math>\{+1, +1, -1, +1, +1\}</math> is impossible because
 +
of the argument from the first solution.  (Repeat the argument
 +
for the sake of completeness: Assume
 +
<math>P(a_1) = P(a_2) = P(a_3) = P(a_4) = 1</math> and <math>P(b_1) = -1</math>.
 +
Then <math>P(x) = (x - a_1)(x - a_2)(x - a_3)(x - a_4) Q(x) + 1</math>
 +
with <math>Q(x)</math> having integer coefficients. Substituting <math>x = b_1</math>
 +
we have <math>(b_1 - a_1)(b_1 - a_2)(b_1 - a_3)(b_1 - a_4) Q(b_1) = -2</math>.
 +
It follows that the values of the four factors <math>(b_1 - a_i)</math> must
 +
be in <math>\{-2, -1, 1, 2\}</math>.  Since they are distinct, they must be
 +
exactly these four values.  Then
 +
<math>(b_1 - a_1)(b_1 - a_2)(b_1 - a_3)(b_1 - a_4) Q(b_1)</math> will be
 +
a multiple of 4, and it can not equal <math>-2</math>.)
 +
 +
The fact that the sequence <math>\{+1, -1, +1, -1, +1\}</math> is impossible
 +
will follow from the additional challenge <math>\mathbf{c}</math>.
 +
 +
 +
  
  

Revision as of 20:41, 27 October 2025

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 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.

$\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$ behind a more general sounding statement. Had it been formulated to state the essence, it would have been much less intimidating, and easier, because the essence would have pointed towards a solution.

Here is a reformulation the problem:

$\mathbf{Problem\ 2}$ Let $P(x)$ be a polynomial 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, we have the stronger bound $m = m_1 + m_2 \le 4$.

$\mathbf{b.}$ If $d = 2$, find $P(x)$ so that there are $4$ distinct integer roots of $P(x) - 1 = 0$ and $P(x) + 1 = 0$.

$\mathbf{c.}$ If $d \ge 3$ and both $m_1 \ge 1, m_2 \ge 1$, then we can not have $m_1 \ge 2$ and $m_2 \ge 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 $\delta = \pm 1$, in the sense that $\delta$ can stand for either of the two values. 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$.

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$.

Now let us look at the solutions $\{s_i\}$ and the values $\{\delta_i = P(s_i)\}$:

$s_1 < s_2 < \dots < s_{m-1} < s_m$

$\delta_1\ \ \ \ \ \delta_2\ \ \ \ \dots\ \ \ \ \delta_{m-1}\ \ \ \ \delta_m$

Note that if for an $i$ the root $s_i = a_j$ for some $j$ then at most two $s_{i'}$ to the right and at most two to the left can be $b_k$ for some $k$ (otherwise the distance from $a_j = s_i$ to them would be $> 2$). In terms of $\{\delta_i\}$ this says that if we have a $+1$ in the sequence, at most two to the right and two to the left can be $-1$. Similarly, if we have a $-1$, at most two to the right and two to the left can be $+1$.

This proves that if the sequence $\{\delta_i\}$ contains both $+1$ and $-1$, its length can be at most $5$. Indeed, if it were of length $\ge 6$, it would contain a $+1$ and a $-1$ at distance $\ge 2$.

This finishes the proof of problem 2.

$\mathbf{Note}$ Just in case this is not clear enough: assume we have a sequence $\{\delta_1, \delta_2, \delta_3, \delta_4, \delta_5, \delta_6\}.$ Assume $\delta_1 = +1$. Since we must have at least one $-1$, take it to be as far as possible, say $\delta_3 = -1$. Then $\delta_6 = -1$ because otherwise, if $\delta_6 = +1$, it would be more than $2$ away from $\delta_3 = -1$. But then $\delta_6 = -1$ is more than $2$ away from $\delta_1 = +1$.

If we took $\delta_2 = -1$, a similar argument would show that we can not have a sequence of $6$ values of $+1$ and $-1$ such that there are no two entries with opposing sign more that $2$ away from each other.

$\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.}$ We have the stronger bound $m = m_1 + m_2 \le 4$.

Indeed, let us look at the sequence $\{\delta_1, \delta_2, \delta_3, \delta_4, \delta_5\}.$ We can assume $\delta_1 = +1$. If $\delta_2 = -1$, then $\delta_5$ must be $-1$ (otherwise $\delta_5 = +1$ would be at distance $> 2$ from $\delta_2 = -1$. But then $\delta_5 = -1$ is at distance $> 2$ from $\delta_1 = +1$.

(To make this more intuitive, I just proved that we can not have the sequence $\{+1, -1, +1, +1, -1\}$.)

However, in principle, we could have the sequences $\{+1, +1, -1, +1, +1\}$ and $\{+1, -1, +1, -1, +1\}.$

The first one, $\{+1, +1, -1, +1, +1\}$ 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$.)

The fact that the sequence $\{+1, -1, +1, -1, +1\}$ is impossible will follow from the additional challenge $\mathbf{c}$.






[TO BE CONTINUED]

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

See Also

1974 IMO (Problems) • Resources
Preceded by
Problem 5 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Last Question
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1974_IMO_Problems/Problem_6&oldid=264279"