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

Latest revision as of 00: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 1: / Line 1: @@
 ==Problem==
 Let <math>P</math> be a non-constant polynomial with integer coefficients. If <math>n(P)</math> is the number of distinct integers <math>k</math> such that <math>(P(k))^2=1,</math> prove that <math>n(P)-\deg(P)\le2,</math> where <math>\deg(P)</math> denotes the degree of the polynomial <math>P.</math>
 ==Solution==
-{{solution}}
+Lemma: Let <math>P(x)</math> be a polynomial with integer coefficients which is not constant. Then if <math>P(x)</math> obtains <math>1</math> (or <math>-1</math>) as its values for at least four times then <math>P(x)\neq -1</math> ( or <math>P(x)\neq 1</math>) for all <math>x</math>.
+Proof. Assume that <math>P(a)=P(b)=P(c)=P(d)=1</math> for <math>a,b,c,d</math> distince. Then if there's <math>u</math> which <math>P(u)=-1</math> then <math>2=P(a)-P(u)=...</math> so <math>P(x)-P(u)-2=(x-a)(x-b)(x-c)(x-d)Q(x)</math> where <math>Q(x)</math> is a polynomial with the integer coefficients! So
+<math>-2=(u-a)(u-b)(u-c)(u-d)Q(u)</math> which is impossible cause <math>-2</math> can not presents as product of more than three distince numbers! This proved the lemma!
+Back to our problem: For convinet put <math>m=n(P)</math> and <math>n=\deg P</math>. Firstly if <math>n\leq 2</math> then <math>m-n\leq2</math>. Assume <math>n\geq3</math>. If equation <math>P(x)=1</math> with more than three integer points (ie.. at least <math>4</math>) then equation <math>(P(x))^2=1</math> implies <math>P(x)=1</math> so <math>m\leq n</math>, ie... <math>m-n\leq 0\leq2</math>. The same case for equation <math>P(x)=-1</math>. So <math>m\leq 6</math>. If <math>n\geq4</math> then <math>m-n\leq 6-n\leq 2</math>. Now assume that <math>n=3</math>. In this case if <math>m\leq 5</math> then <math>m-n\leq 2</math>.
+So let us show that <math>m<6</math>. In fact if <math>m=6</math> then <math>P(x)-1=0</math> has three integers distince roots, and the same for <math>P(x)+1=0</math>. So
+<math>P(x)-1=k_1(x-a_1)(x-a_2)(x-a_3)</math> and <math>P(x)+1=k_2(x-b_1)(x-b_2)(x-b_3)</math> where <math>a_i</math> distince and <math>b_j</math> distince and all with <math>k_1,k_2</math> are integers! Then
+<math>k_2(x-b_1)(x-b_2)(x-b_3)-k_1(x-a_1)(x-a_2)(x-a_3)=2</math> for all <math>x</math>. So <math>k_1=k_2=k</math>.
+Finally, we have
+<math>2=k(a_i-b_1)(a_i-b_2)(a_i-b_3)</math> for <math>i=1,2,3</math> and because that <math>\pm1</math> can not presents as products of three distince numbers so <math>k=\pm1</math>, we may assume <math>k=1</math>. Because <math>2=(-2)\cdot 1\cdot -1</math> so
+<math>\{-2,1,-1\}=\{a_i-b_1,a_i-b_2,a_i-b_3\}</math>
+This means <math>3a_i-(b_1+b_2+b_3)=-2+1-1=-2</math>. So we must have <math>3a_1=3a_2=3a_3</math> which follows <math>a_1=a_2=a_3</math>, which contracts!. So <math>m\leq 5</math> and we're done.
+The above solution was posted and copyrighted by pluricomplex.
+==Remarks (added by pf02, October 2025)==
+<math>\mathbf{1.}</math>  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:
+<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
+the other has no integer solutions.
+<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>.
+The statement of the original problem is a trivial consequence
+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
+of the distinct, integer solutions of <math>P(x) - 1 = 0</math> and
+<math>P(x) + 1 = 0</math>.  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 <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\ (a\ better\ version\ of\ the\ problem)}</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>n(P) = m = m_1 + m_2 \le 4</math>.
+==Solution 2 (solution of the better problem)==
+If <math>\deg(P) = 1</math> or <math>\deg(P) = 2</math> the statement is obviously true.
+So, assume <math>\deg(P) \ge 3</math>.
+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>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>.  We will think of the sequence <math>M</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
+<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 any solution of <math>P(x) - 1 = 0</math>
+and any solution of <math>P(x) + 1 = 0</math> are at distance at most <math>2</math>.
+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.
+It follows that <math>M</math> can not have <math>6</math> (or more) elements.
+Indeed, assume that <math>M</math> has <math>6</math> elements
+<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>.
+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 what we proved so far.  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 <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 = \deg(P) \ge 3</math> then <math>n(P) = m \le 5 \le d + 2</math>.
+Let us prove the stronger bound <math>m = m_1 + m_2 \le 4</math>.
+Assume that <math>m = m_1 + m_2 = 5</math>.  Then we have that <math>m_1, m_2</math> are <math>4</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).
+Assume <math>m_1 = 4, m_2 = 1</math>.  This 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>.)
+Now assume <math>m_1 = 3, m_2 = 2</math>.  Looking again at
+<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]
+The original thread for this problem can be found here: [https://aops.com/community/p364890]
 ==See Also==
 {{IMO box|year=1974|num-b=5|after=Last Question}}
-[[Category:Olympiad Geometry Problems]]
+[[Category:Olympiad Algebra Problems]]

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