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 27: Line 27:
 
<math>\mathbf{1.}</math>  The solution above is written very sloppily and
 
<math>\mathbf{1.}</math>  The solution above is written very sloppily and
 
badly, it could use substantial editing.  However, the proof is
 
badly, it could use substantial editing.  However, the proof is
−
understandable, and I will refrain from
+
understandable and correct, and I will refrain from rewriting it.
−
rewriting it.
 
  
 
It is interesting to note that it actually proves substantially
 
It is interesting to note that it actually proves substantially
Line 42: Line 41:
  
 
The statement of the original problem is a trivial consequence
 
The statement of the original problem is a trivial consequence
−
of these statements.
+
of these statements (as I will show later).
  
 
<math>\mathbf{2.}</math>  This problem is in fact very easy.  It is made
 
<math>\mathbf{2.}</math>  This problem is in fact very easy.  It is made
−
difficult artificially by hiding the essence of the description
+
difficult artificially, by hiding the essence of the description
 
of the distinct, integer solutions of <math>P(x) - 1 = 0</math> and
 
of the distinct, integer solutions of <math>P(x) - 1 = 0</math> and
−
<math>P(x) + 1 = 0</math> behind a more general sounding statement.  Had
+
<math>P(x) + 1 = 0</math>.  The essence is hidden  behind a more general
−
it been formulated to state the essence, it would have been
+
sounding (in some sense artificial) statement.  Had it been
−
much less intimidating, and easier, because the essence would
+
formulated to express the essence of the description of the
−
have pointed towards a solution.
+
distinct, integer roots of <math>P(x) - 1 = 0</math> and <math>P(x) + 1 = 0</math>,
 +
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:
 
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 with integer
−
Let <math>m_1 =</math> the number of distinct integer roots of <math>P(x) - 1 = 0</math>,
+
coefficients of degree <math>d \ge 3</math>. Let <math>m_1 =</math> the number of
−
and <math>m_2 =</math> the number of distinct integer roots of <math>P(x) + 1 = 0</math>.
+
distinct integer roots of <math>P(x) - 1 = 0</math>, and <math>m_2 =</math> the number
−
If both <math>m_1 \ge 1, m_2 \ge 1</math> then <math>m = m_1 + m_2 \le 5</math>.
+
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>.
  
 
<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, assume we have a
−
bound <math>m = m_1 + m_2 \le 4</math>.
+
non-constant polynomial <math>P(x)</math> with constant coefficients, and
 +
assume <math>m_1 \ge 1, m_2 \ge 1</math>.  Prove the stronger 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>, give an example of <math>P(x)</math> for which there
−
integer roots of <math>P(x) - 1 = 0</math> and <math>P(x) + 1 = 0</math>.
+
are <math>4</math> distinct integer roots of <math>P(x) - 1 = 0</math> and <math>P(x) + 1 = 0</math>.
 +
 
 +
<math>\mathbf{c.}</math>  If <math>d = 3</math>, give an example of <math>P(x)</math> for which there
 +
are <math>3</math> distinct integer roots of <math>P(x) - 1 = 0</math> and one root of
 +
<math>P(x) + 1 = 0</math>.
 +
 
 +
<math>\mathbf{d.}</math>  If <math>d = 3</math> show that it is impossible to have <math>m_1 = 2</math>
 +
and <math>m_2 = 2</math>.
  
−
<math>\mathbf{c.}</math>  If <math>d \ge 3</math> and both <math>m_1 \ge 1, m_2 \ge 1</math>, then we
 
−
can not have <math>m_1 \ge 2</math> and <math>m_2 \ge 2.</math>
 
  
 
<math>\mathbf{3.}</math>  Below I will prove Problem 2 (from which the.statement
 
<math>\mathbf{3.}</math>  Below I will prove Problem 2 (from which the.statement
−
of the original problem follows trivially), as well as.the additional
+
of the original problem follows trivially), as well as the additional
 
challenges.
 
challenges.
  
Line 83: Line 92:
 
Let <math>M_1 = \{a_1 < \dots < a_{m_1}\}</math> be the integer, distinct solutions
 
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
 
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>,
+
integer, distinct solutions of <math>P(x) + 1 = 0</math>.  Denote
−
in the sense that <math>\delta</math> can stand for either of the two values.
+
<math>M = \{s_1 < \dots < s_m\}</math> the union <math>M_1 \cup M_2</math> arranged in
−
Denote <math>M = \{s_1 < \dots < s_m\}</math> the union <math>M_1 \cup M_2</math> arranged
+
increasing order.  Thus each <math>s_i</math> could be an element <math>a_j \in M_1</math>
−
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>.  We will just look at the sequence <math>M</math>
−
or an element <math>b_k \in M_2</math>.
+
as a sequence of <math>a</math>'s and <math>b</math>'s.
  
 
Let <math>a</math> satisfy <math>P(a) - 1 = 0</math> and <math>b</math> satisfy <math>P(b) + 1 = 0</math>.  Then
 
Let <math>a</math> satisfy <math>P(a) - 1 = 0</math> and <math>b</math> satisfy <math>P(b) + 1 = 0</math>.  Then
Line 96: Line 105:
 
and a solution of <math>P(x) + 1 = 0</math> are at distance at most <math>2</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
+
In terms of looking at <math>M</math> as a sequence of <math>a</math>'s and <math>b</math>'s, given that
−
<math>\{\delta_i = P(s_i)\}</math>:
+
all the <math>s_i</math>'s are distinct, this tells us that the distance in the
−
 
+
counting (or indexing) in the sequence, any <math>b</math> is at most two away from
−
<math>s_1      <         s_2    <     \dots <       s_{m-1}    <     s_m</math>
+
any <math>a</math>.  In other words, if we have an <math>a</math>, then at most two entries to
 +
the right and two entries to the left are <math>b</math>'s, and similarly, if we
 +
have a <math>b</math>, then at most two entries to the right and two entries to the
 +
left are <math>a</math>'s.
  
−
<math>\delta_1\ \ \ \ \ \delta_2\ \ \ \ \dots\ \ \ \ \delta_{m-1}\ \ \ \ \delta_m</math>
+
It follows that <math>M</math> can not have <math>6</math> (or more) elements.
  
−
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
+
Indeed, <math>m</math> has <math>6</math> elements and assume <math>s_1</math> is an <math>a</math>.  Then
−
<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>
+
<math>s_4, s_5, s_6</math> must be <math>a</math>'s.  Since <math>s_6</math> is an <math>a</math>, <math>s_2, s_3</math>
−
(otherwise the distance from <math>a_j = s_i</math> to them would be <math>> 2</math>).  In terms
+
must be <math>a</math>'s.  It follows that all <math>s_i</math>'s are <math>a</math>'s, which is a
−
of <math>\{\delta_i\}</math> this says that if we have a <math>+1</math> in the sequence, at most
+
contradiction since we assumed we have at least one <math>b</math>.
−
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>,
+
<math>\mathbf{Note}</math> This argument does not exclude <math>m = 5</math>.  For example,
−
its length can be at most <math>5</math>.  Indeed, if it were of length <math>\ge 6</math>, it
+
we could have a sequence <math>M = \{a, a, b, a, a\}</math>.
−
would contain a <math>+1</math> and a <math>-1</math> at distance <math>\ge 2</math>.
 
  
 
This finishes the proof of problem 2.
 
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
 
<math>\mathbf{Note}</math>  The statement of the original problem follows trivially
Line 136: Line 133:
 
<math>\mathbf{Proof\ of\ the\ additional\ challenges}</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>.
+
<math>\mathbf{a.}</math> Let us prove 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
+
Assume that <math>m = m_1 + m_2 = 5</math>.  Then we have that <math>m_1, m_2</math> are <math>4</math>
−
<math>\{+1, +1, -1, +1, +1\}</math> and <math>\{+1, -1, +1, -1, +1\}.</math>
+
and <math>1</math> (in some order), or <math>m_1, m_2</math> are <math>3</math> and <math>2</math> (in some order).
  
−
The first one, <math>\{+1, +1, -1, +1, +1\}</math> is impossible because
+
Assume <math>m_1 = 4, m_2 = 1</math>.  This is impossible because of the argument
−
of the argument from the first solution.  (Repeat the argument
+
from the first solution.  (Repeat the argument
 
for the sake of completeness: Assume
 
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>.
 
<math>P(a_1) = P(a_2) = P(a_3) = P(a_4) = 1</math> and <math>P(b_1) = -1</math>.
Line 164: Line 151:
 
a multiple of 4, and it can not equal <math>-2</math>.)
 
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
+
Now assume <math>m_1 = 3, m_2 = 2</math>.  Then
−
will follow from the additional challenge <math>\mathbf{c}</math>.
+
<math>P(x) = (x - a_1)(x - a_2)(x - a_3) Q_1(x) + 1</math> and
 +
<math>P(x) = (x - b_1)(x - b_2) Q_2(x) + 1</math> for some <math>a_1, a_2, a_3, b_1, b_2</math>
 +
(all distinct), and <math>Q_1(x), Q_2(x)</math> some polynomials with integer
 +
coefficients.  Then
 +
<math>(x - a_1)(x - a_2)(x - a_3) Q_1(x) - (x - b_1)(x - b_2) Q_2(x) = -2</math>.
 +
 
 +
Substituting <math>x = b_1, b_2</math> we have
 +
 
 +
<math>(b_1 - a_1)(b_1 - a_2)(b_1 - a_3) Q_1(b_1) = -2</math>
 +
 
 +
<math>(b_2 - a_1)(b_2 - a_2)(b_2 - a_3) Q_1(b_1) = -2</math>
 +
 
 +
Then each <math>(b_j - a_i)</math> must equal one of <math>-2, -1, 1, 2</math>.
 +
We now need to make a very careful analysis of all the cases
 +
when <math>(b_j - a_i)</math> take all the possible values.  Approached
 +
with brute force, there would be <math>4^6 = 4096</math> cases, but we
 +
can reduce this enormously.
 +
 
 +
Think of listing the <math>6</math> entries, in two groups of <math>3</math>
 +
 
 +
<math>(b_1 - a_1)\ \ (b_1 - a_2)\ \ (b_1 - a_3)\ \ \ \ (b_2 - a_1)\ \ (b_2 - a_2)\ \ (b_2 - a_3)</math>
 +
 
 +
The values of the entries in the first group of <math>3</math> have to be
 +
distinct, and the values of the entries in the second group of
 +
<math>3</math> 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 <math>2</math> and <math>-2</math> within the same group of <math>3</math> entries.
 +
 
 +
Two triplets of values in a group which differ by a sign are
 +
equivalent (e.g. <math>1, -1, 2</math> and <math>-1, 1, -2</math>).
 +
 
 +
The idea of the proof is to list all the relevant choices for
 +
<math>(b_j - a_i)</math>, and see that the choice of values leads to a
 +
contradiction.  The final check will be to verify whether
 +
<math>(b_1 - a_1) - (b_1 - a_2) = (b_2 - a_1) - (b_2 - a_2)</math>
 +
and <math>(b_1 - a_2) - (b_1 - a_3) = (b_2 - a_2) - (b_2 - a_3)</math>.
 +
 
 +
It will turn out that it is impossible to choose values for the
 +
two groups of <math>6</math> 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.
 +
 
 +
 
 +
 
  
  

Revision as of 18:43, 28 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 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]

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=264350"