Difference between revisions of "1974 IMO Problems/Problem 6"

Latest revision as of 01:12, 29 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 (and 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\ (a\ better\ version\ of\ the\ problem)}$ Let $P(x)$ be a polynomial with integer coefficients. 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 $n(P) = m = m_1 + m_2 \le 4$ .

Solution 2 (solution of the better problem)

If $\deg(P) = 1$ or $\deg(P) = 2$ the statement is obviously true. So, assume $\deg(P) \ge 3$ .

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 think of 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 any solution of $P(x) - 1 = 0$ and any 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 in terms of the distance in the counting (or indexing) in the sequence, any $b$ is at most two away from any $a$ , and any $a$ is at most $2$ away from any $b$ . 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, 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, assume that $M$ has $6$ elements $M = \{s_1 < s_2 < s_3 < s_4 < s_5 < s_6\}$ 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}$ The statement of the original problem follows trivially from what we proved so far. 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 $\deg(P)$ is $1$ or $2$ , then $n(P) \le 2, 4$ respectively, which is less than $d + 2$ . If the degree $d = \deg(P) \ge 3$ then $n(P) = m \le 5 \le d + 2$ .

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$ . Looking again at $M = \{s_1 < s_2 < s_3 < s_4 < s_5\}$ as a sequence of $a$ 's and $b$ 's, assume that $s_1$ is an $a$ . Then $s_4, s_5$ must be $a$ 's. If $s_5$ is an $a$ , then $s_2$ must be an $a$ . Depending on $s_3$ , either $M$ has only $a$ 's, which is impossible, or $M = \{a, a, b, a, a\}$ . This would put us in the case $m_1 = 4, m_2 = 1$ , which is a contradiction.

The assumption $m = m_1 + m_2 = 5$ led to a contradiction, so $m \le 4$ .

[Solution by pf02, October 2025]

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

@@ Line 27: / Line 27: @@
 <math>\mathbf{1.}</math>  The solution above is written very sloppily and
 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
@@ Line 42: / Line 41: @@
 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
-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
-<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 (and 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:
-<math>\mathbf{Problem\ 2}</math>  Let <math>P(x)</math> be a polynomial of degree <math>d \ge 3</math>.
+<math>\mathbf{Problem\ 2\ (a\ better\ version\ of\ the\ problem)}</math>
-Let <math>m_1 =</math> the number of distinct integer roots of <math>P(x) - 1 = 0</math>,
+Let <math>P(x)</math> be a polynomial with integer coefficients.  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>.
-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>n(P) = m = m_1 + m_2 \le 4</math>.
-<math>\mathbf{Additional\ challenges}</math>
-<math>\mathbf{a.}</math>  With the notation of Problem 2, we have the stronger
+==Solution 2 (solution of the better problem)==
-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
+If <math>\deg(P) = 1</math> or <math>\deg(P) = 2</math> the statement is obviously true.
-integer roots of <math>P(x) - 1 = 0</math> and <math>P(x) + 1 = 0</math>.
+So, assume <math>\deg(P) \ge 3</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
-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 <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>,
+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 think of the sequence <math>M</math> as a
-or an element <math>b_k \in M_2</math>.
+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
@@ Line 93: / Line 79: @@
 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>
+of <math>2</math>.  We paraphrase this by saying that any 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>.
+and any 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.
+In terms of looking at <math>M</math> as a sequence of <math>a</math>'s and <math>b</math>'s, given that
+all the <math>s_i</math>'s are distinct, this tells us that in terms of the distance
+in the counting (or indexing) in the sequence, any <math>b</math> is at most two away
+from any <math>a</math>, and any <math>a</math> is at most <math>2</math> away from any <math>b</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, 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>\mathbf{Note}</math>  Just in case this is not clear enough: assume we have
+It follows that <math>M</math> can not have <math>6</math> (or more) elements.
-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
+Indeed, assume that <math>M</math> has <math>6</math> elements
-have a sequence of <math>6</math> values of <math>+1</math> and <math>-1</math> such that there are no two
+<math>M = \{s_1 < s_2 < s_3 < s_4 < s_5 < s_6\}</math> and assume <math>s_1</math> is an <math>a</math>.
-entries with opposing sign more that <math>2</math> away from each other.
+Then <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>
+must be <math>a</math>'s.  It follows that all <math>s_i</math>'s are <math>a</math>'s, which is a
+contradiction since we assumed we have at least one <math>b</math>.
 <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>
+from what we proved so far.  Indeed, if only one of <math>P(x) - 1 = 0</math> and
-has integer roots, then <math>n(P) \le d < d + 2</math>.  If the degree <math>d</math> of <math>P(x)</math>
+<math>P(x) + 1 = 0</math> has integer roots, then <math>n(P) \le d < d + 2</math>.  If <math>\deg(P)</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>.
+If the degree <math>d = \deg(P) \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>.
+Let us prove the stronger bound <math>m = m_1 + m_2 \le 4</math>.
-Indeed, let us look at the sequence
+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>\{\delta_1, \delta_2, \delta_3, \delta_4, \delta_5\}.</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).
-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
+Assume <math>m_1 = 4, m_2 = 1</math>.  This is impossible because of the argument
-have the sequence <math>\{+1, -1, +1, +1, -1\}</math>.)
+from the first solution.  (Repeat the argument
-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>.
@@ Line 164: / Line 122: @@
 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>.  Looking again at
-will follow from the additional challenge <math>\mathbf{c}</math>.
+<math>M = \{s_1 < s_2 < s_3 < s_4 < s_5\}</math> as a sequence of <math>a</math>'s and <math>b</math>'s,
+assume that <math>s_1</math> is an <math>a</math>.  Then <math>s_4, s_5</math> must be <math>a</math>'s.  If <math>s_5</math>
+is an <math>a</math>, then <math>s_2</math> must be an <math>a</math>.  Depending on <math>s_3</math>, either
+<math>M</math> has only <math>a</math>'s, which is impossible, or <math>M = \{a, a, b, a, a\}</math>.
+This would put us in the case <math>m_1 = 4, m_2 = 1</math>, which is a
+contradiction.
+The assumption <math>m = m_1 + m_2 = 5</math> led to a contradiction, so <math>m \le 4</math>.
+[Solution by pf02, October 2025]
-[TO BE CONTINUED]
 The original thread for this problem can be found here: [https://aops.com/community/p364890]

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