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"

m (→‎Resources)
 
(12 intermediate revisions by 5 users not shown)
Line 2: Line 2:
  
 
Let <math>a</math>, <math>b</math>, and <math>c</math> denote three distinct integers, and let <math>P</math> denote a polynomial having all integral coefficients.  Show that it is impossible that <math>P(a)=b</math>, <math>P(b)=c</math>, and <math>P(c)=a</math>.
 
Let <math>a</math>, <math>b</math>, and <math>c</math> denote three distinct integers, and let <math>P</math> denote a polynomial having all integral coefficients.  Show that it is impossible that <math>P(a)=b</math>, <math>P(b)=c</math>, and <math>P(c)=a</math>.
 +
 +
 +
== Hint ==
 +
 +
If <math>P</math> is a polynomial with integral coefficients, then <cmath>a - b | P(a) - P(b).</cmath> (Why?)
  
 
== Solution ==
 
== Solution ==
Line 13: Line 18:
 
so <math>a=b= P(a)</math>, and <math>c= P(b) = P(a) = b</math>, so <math>a</math>, <math>b</math>, and <math>c</math> are equal, as desired.  <math>\blacksquare</math>
 
so <math>a=b= P(a)</math>, and <math>c= P(b) = P(a) = b</math>, so <math>a</math>, <math>b</math>, and <math>c</math> are equal, as desired.  <math>\blacksquare</math>
  
 +
===Solution 1b===
 +
Let <math>k</math> be the value <math>(a-b), (b-c), (c-a)</math> are equal to in absolute value. Assume <math>k</math> is nonzero. Then each of <math>(a-b), (b-c), (c-a)</math> is equal to <math>k</math> or <math>-k</math>, so <cmath>0 = (a-b) + (b-c) + (c-a) = mk,</cmath> where <math>m</math> is one of -3, -1, 1, or 3. In particular, neither <math>m</math> nor <math>k</math> is zero, contradiction. Hence, <math>k = 0</math>, and <math>a, b, c</math> are equal, yielding a final contradiction of the existence of these variables. <math>\blacksquare</math>
 +
 +
In fact, this approach generalizes readily. Suppose that <math>n</math> is an odd integer, and that there exist <math>n</math> distinct integers <math>a_1, a_2, ..., a_n</math> such that <math>P(a_i) = a_{i+1}</math> and <math>P(a_n) = 1</math>, for <math>1 \le i \le n-1</math>. Then we have <cmath>a_1 - a_2 | a_2 - a_3 | ... | a_n - a_1 | a_1 - a_2,</cmath> so the differences are all equal in absolute value and thus equal to <math>k</math> or <math>-k</math> for some integer <math>k</math>. Adding the differences (in the order they are written) gives <math>0 = mk</math> for some odd integer <math>m</math>, so <math>m</math> is nonzero and hence <math>k = 0</math>. Thus, all the <math>a_i</math> are equal, a contradiction of their distinctness, so the sequence <math>a_i</math> cannot exist.
 +
 +
==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.
 +
 +
==Solution 3==
 +
Assume for the sake of contradiction that is possible for unique integers <math>a,b,c</math>. Let <math>P(x)=d_1x^n+d_2x^{n-1}+\cdots+d_n.</math> Note that  <cmath>b=P(a)=d_1a^n+d_2a^{n-1}+\cdots+d_n</cmath>
 +
<cmath>c=P(b)=d_1b^n+d_2b^{n-1}+\cdots+d_n</cmath>
 +
<cmath>a=P(c)=d_1c^n+d_2c^{n-1}+\cdots+d_n</cmath>
 +
Subtracting the second from the first, third from second, and first from third gives
 +
<cmath>b-c=P(a)-P(b)=d_1(a^n-b^n)+d_2(a^{n-1}-b^{n-1})+\cdots+ d_{n-1}(a-b)</cmath>
 +
<cmath>c-a=P(b)-P(c)=d_1(b^n-c^n)+d_2(b^{n-1}-c^{n-1})+\cdots +d_{n-1}(b-c)</cmath>
 +
<cmath>a-b=P(c)-P(a)=d_1(c^n-a^n)+d_2(c^{n-1}-a^{n-1})+\cdots +d_{n-1}(c-a)</cmath> By the RHS, note that <math>a-b\mid P(a)-P(b)</math> so <math>\lvert{a-b}\rvert\leq\lvert{b-c}\rvert.</math>  Similarly, <math>\lvert{b-c}\rvert\leq\lvert{c-a}\rvert</math> and <math>\lvert{c-a}\rvert\leq\lvert{a-b}\rvert.</math>  Hence, <math>\lvert{a-b}\rvert\leq\lvert{b-c}\rvert\leq\lvert{c-a}\rvert\leq\lvert{a-b}\rvert</math> so <math>\lvert{a-b}\rvert=\lvert{b-c}\rvert=\lvert{c-a}\rvert.</math>  Assume WLOG that <math>a>b>c</math> so <math>a-b=a-c</math> and <math>b-c=c-a.</math>  From the first equation, we get <math>b=c</math> and substituting this in the second gives <math>c=a.</math>  Hence, <math>a=b=c</math>, contradicting the uniqueness of <math>a,b,c.</math> <math>\blacksquare</math>
 +
 +
==Solution 4==
 +
 +
Assume that <math>a, b</math> and <math>c</math> are distinct integers which satisfy the given conditions. Then we have <math>P(c) = P(P(b)) = P(P(P(a))) = a</math>. Similarly <math>P(P(P(b))) = b</math> and <math>P(P(P(c))) = c</math>. Since the polynomial has integer coefficients, this implies that the polynomial <math>P</math> is <math>P(x) = x</math>. But this is a contradiction since then <math>P(a) = b</math> can only be true if <math>a = b</math> which contradicts the fact that <math>a, b</math> and <math>c</math> are distinct integers.
  
 +
==Solution 5==
 +
We get that <math>a-b|b-c, b-c|c-a, c-a|a-b</math>. Thus, we can say that <math>(b-c) = (a-b)k, (c-a) = (b-c)j, (a-b) = (c-a)m</math>, for non zero integers, not necesarily positive, k, j, and m. Multiplying these equations and canceling, we get that <math>kjm</math>=1. This means that either k=1, m=1, j=1, or two of the variables are equal to 1 and the other is equal to -1. If all of the variables are equal to zero, plugging in gives us that <math>a=b=c</math>, contradictory to the conditions given in the problem statement. If two of the variables are equal to -1, and the other is equal to 1, then WLOG let <math>k=m=-1, j=1</math>. But this implies that the distinct integer condition is not satisfied, and hence, this case is invalid. Thus, it is impossible. <math>\blacksquare</math>
 
{{alternate solutions}}
 
{{alternate solutions}}
  
 
== See Also ==
 
== See Also ==
  
−
{{USAMO box|year=1974|beforetext=|before=First Problem|num-a=2}}
+
{{USAMO box|year=1974|beforetext=|before=First Question|num-a=2}}
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=579731#579731 Discussion on AoPS/MathLinks]
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=579731#579731 Discussion on AoPS/MathLinks]
 +
{{MAA Notice}}
  
  
 
[[Category:Olympiad Algebra Problems]]
 
[[Category:Olympiad Algebra Problems]]

Latest revision as of 20:30, 27 April 2020

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$.


Hint

If $P$ is a polynomial with integral coefficients, then \[a - b | P(a) - P(b).\] (Why?)

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 1b

Let $k$ be the value $(a-b), (b-c), (c-a)$ are equal to in absolute value. Assume $k$ is nonzero. Then each of $(a-b), (b-c), (c-a)$ is equal to $k$ or $-k$, so \[0 = (a-b) + (b-c) + (c-a) = mk,\] where $m$ is one of -3, -1, 1, or 3. In particular, neither $m$ nor $k$ is zero, contradiction. Hence, $k = 0$, and $a, b, c$ are equal, yielding a final contradiction of the existence of these variables. $\blacksquare$

In fact, this approach generalizes readily. Suppose that $n$ is an odd integer, and that there exist $n$ distinct integers $a_1, a_2, ..., a_n$ such that $P(a_i) = a_{i+1}$ and $P(a_n) = 1$, for $1 \le i \le n-1$. Then we have \[a_1 - a_2 | a_2 - a_3 | ... | a_n - a_1 | a_1 - a_2,\] so the differences are all equal in absolute value and thus equal to $k$ or $-k$ for some integer $k$. Adding the differences (in the order they are written) gives $0 = mk$ for some odd integer $m$, so $m$ is nonzero and hence $k = 0$. Thus, all the $a_i$ are equal, a contradiction of their distinctness, so the sequence $a_i$ cannot exist.

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.

Solution 3

Assume for the sake of contradiction that is possible for unique integers $a,b,c$. Let $P(x)=d_1x^n+d_2x^{n-1}+\cdots+d_n.$ Note that \[b=P(a)=d_1a^n+d_2a^{n-1}+\cdots+d_n\] \[c=P(b)=d_1b^n+d_2b^{n-1}+\cdots+d_n\] \[a=P(c)=d_1c^n+d_2c^{n-1}+\cdots+d_n\] Subtracting the second from the first, third from second, and first from third gives \[b-c=P(a)-P(b)=d_1(a^n-b^n)+d_2(a^{n-1}-b^{n-1})+\cdots+ d_{n-1}(a-b)\] \[c-a=P(b)-P(c)=d_1(b^n-c^n)+d_2(b^{n-1}-c^{n-1})+\cdots +d_{n-1}(b-c)\] \[a-b=P(c)-P(a)=d_1(c^n-a^n)+d_2(c^{n-1}-a^{n-1})+\cdots +d_{n-1}(c-a)\] By the RHS, note that $a-b\mid P(a)-P(b)$ so $\lvert{a-b}\rvert\leq\lvert{b-c}\rvert.$ Similarly, $\lvert{b-c}\rvert\leq\lvert{c-a}\rvert$ and $\lvert{c-a}\rvert\leq\lvert{a-b}\rvert.$ Hence, $\lvert{a-b}\rvert\leq\lvert{b-c}\rvert\leq\lvert{c-a}\rvert\leq\lvert{a-b}\rvert$ so $\lvert{a-b}\rvert=\lvert{b-c}\rvert=\lvert{c-a}\rvert.$ Assume WLOG that $a>b>c$ so $a-b=a-c$ and $b-c=c-a.$ From the first equation, we get $b=c$ and substituting this in the second gives $c=a.$ Hence, $a=b=c$, contradicting the uniqueness of $a,b,c.$ $\blacksquare$

Solution 4

Assume that $a, b$ and $c$ are distinct integers which satisfy the given conditions. Then we have $P(c) = P(P(b)) = P(P(P(a))) = a$. Similarly $P(P(P(b))) = b$ and $P(P(P(c))) = c$. Since the polynomial has integer coefficients, this implies that the polynomial $P$ is $P(x) = x$. But this is a contradiction since then $P(a) = b$ can only be true if $a = b$ which contradicts the fact that $a, b$ and $c$ are distinct integers.

Solution 5

We get that $a-b|b-c, b-c|c-a, c-a|a-b$. Thus, we can say that $(b-c) = (a-b)k, (c-a) = (b-c)j, (a-b) = (c-a)m$, for non zero integers, not necesarily positive, k, j, and m. Multiplying these equations and canceling, we get that $kjm$=1. This means that either k=1, m=1, j=1, or two of the variables are equal to 1 and the other is equal to -1. If all of the variables are equal to zero, plugging in gives us that $a=b=c$, contradictory to the conditions given in the problem statement. If two of the variables are equal to -1, and the other is equal to 1, then WLOG let $k=m=-1, j=1$. But this implies that the distinct integer condition is not satisfied, and hence, this case is invalid. Thus, it is impossible. $\blacksquare$ 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=121758"