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 USAMO Problems/Problem 1"
Line 14: Line 14:
  
  
 +
==Solution 2==
 +
Consider the polynomial <math>Q(x) = (b-a)P(x) - (c-b)x - b^2 + ac.</math> By using the facts that <math>P(a) = b</math> and <math>P(b) = c</math>, we find that <math>Q(a) = Q(b) = 0.</math> Thus, the polynomial <math>Q(x)</math> has a and b as roots, and we can write <math>Q(x) = (x-a)(x-b)R(x)</math> for some polynomial <math>R(x)</math>. Because <math>Q(x)</math> and <math>(x-a)(x-b)</math> are monic polynomials with integral coefficients, their quotient, <math>R(x)</math>, must also have integral coefficients, as can be demonstrated by simulating the long division. Thus, <math>Q(c)</math>, and hence <math>Q(c) - (x-a)(x-b)</math>, must be divisible by <math>(c-a)(c-b)</math>. But if <math>x=c-a</math> and <math>y=c-b</math>, then we must have, after rearranging terms and substitution, that <math>(x-y)^2</math> is divisible by <math>xy</math>. Equivalently, <math>S = x^2 + y^2</math> is divisible by <math>xy</math> (after canceling the <math>2xy</math> which is clearly divisble by <math>xy</math>). Because S must be divisible by both x and y, we quickly deduce that x is divisible by y and y is divisible by x. Thus, x and y are equal in absolute value. A similar statement holds for a cyclic pemutation of the variables, and so x, y, and z are all equal in absolute value. The conclusion follows as in the first solution.
  
  

Revision as of 00:12, 4 August 2014

Problem

Let $a$, $b$, and $c$ denote three distinct integers, and let $P$ denote a polynomial having all integral coefficients. Show that it is impossible that $P(a)=b$, $P(b)=c$, and $P(c)=a$.

Solution

It suffices to show that if $a,b,c$ are integers such that $P(a) = b$, $P(b)=c$, and $P(c)= a$, then $a=b=c$.

We note that \[a-b \mid P(a) - P(b) = b-c \mid P(b)-P(c) = c-a \mid P(c) - P(a) = a-b ,\] so the quanitities $(a-b), (b-c), (c-a)$ must be equal in absolute value. In fact, two of them, say $(a-b)$ and $(b-c)$, must be equal. Then \[0 = \lvert (a-b) + (b-c) + (c-a) \rvert = \lvert 2(a-b) + (c-a) \rvert \ge 2 \lvert a-b \rvert - \lvert c-a \rvert = \lvert a-b \rvert ,\] so $a=b= P(a)$, and $c= P(b) = P(a) = b$, so $a$, $b$, and $c$ are equal, as desired. $\blacksquare$


Solution 2

Consider the polynomial $Q(x) = (b-a)P(x) - (c-b)x - b^2 + ac.$ By using the facts that $P(a) = b$ and $P(b) = c$, we find that $Q(a) = Q(b) = 0.$ Thus, the polynomial $Q(x)$ has a and b as roots, and we can write $Q(x) = (x-a)(x-b)R(x)$ for some polynomial $R(x)$. Because $Q(x)$ and $(x-a)(x-b)$ are monic polynomials with integral coefficients, their quotient, $R(x)$, must also have integral coefficients, as can be demonstrated by simulating the long division. Thus, $Q(c)$, and hence $Q(c) - (x-a)(x-b)$, must be divisible by $(c-a)(c-b)$. But if $x=c-a$ and $y=c-b$, then we must have, after rearranging terms and substitution, that $(x-y)^2$ is divisible by $xy$. Equivalently, $S = x^2 + y^2$ is divisible by $xy$ (after canceling the $2xy$ which is clearly divisble by $xy$). Because S must be divisible by both x and y, we quickly deduce that x is divisible by y and y is divisible by x. Thus, x and y are equal in absolute value. A similar statement holds for a cyclic pemutation of the variables, and so x, y, and z are all equal in absolute value. The conclusion follows as in the first solution.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

1974 USAMO (Problems • Resources)
First Question Followed by
Problem 2
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1974_USAMO_Problems/Problem_1&oldid=62726"