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"

(Created page with "==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>(...")
 
 
Line 3: Line 3:
  
 
==Solution==
 
==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. The original thread for this problem can be found here: [https://aops.com/community/p364890]
 
==See Also==
 
==See Also==
  
 
{{IMO box|year=1974|num-b=5|after=Last Question}}
 
{{IMO box|year=1974|num-b=5|after=Last Question}}
 
[[Category:Olympiad Geometry Problems]]
 
[[Category:Olympiad Geometry Problems]]

Latest revision as of 16:02, 29 January 2021

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. 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=143904"