Let $ a,b,$ and $ c$ denote three distinct integers, and let $ P$ denote a polynomial having integer coefficients. Show that it is impossible that $ P(a) = b, P(b) = c,$ and $ P(c) = a$.
Problem
Source: 1974 USAMO Problem 1
Tags: algebra, polynomial, USA(J)MO, USAMO, AIME
13.03.2010 08:24
$ a,b,c \in \mathbb{Z}$, and $ a,b,c$ are distinct. Since we have $ P[\mathbb{Z}]$, suppose we have by the given conditions to be exisitng such that $ a-b | b-c$ $ b-c | c-a$ $ c-a | a-b$. As we are dealing over integers, $ 2b\ge c+a$ $ 2c\ge a+b$ $ 2a\ge b+c$ THis however implies equaltiy holds everywhere and therefore contradiction.
13.03.2010 18:20
I don't think that's directly implied from the divisibilities you've arrived at. What if $ a - b > 0$ and $ b - c < 0$?
13.03.2010 18:40
Agr_94_Math wrote: $ a,b,c \in \mathbb{Z}$, and $ a,b,c$ are distinct. Since we have $ P[\mathbb{Z}]$, suppose we have by the given conditions to be exisitng such that $ a - b | b - c$ $ b - c | c - a$ $ c - a | a - b$. you can arrive the result immediately by using the fact that If $ x|y$ and $ y|x$, then $ |x|=|y|$.
20.04.2010 00:30
Well, thinking about the constant term (let it be z), b=z mod a. Similarly, c= z mod b, a=z mod c. b=z mod a=z mod (z mod(a)) =z mod z-na for some n, which means c=na, and c is a multiple of a. Similarly, a is a multiple of b, and b is in turn a multiple of c, so it follows that they are all equal, as a=1b, b=1c, and c=1a, as otherwise all the numbers would be unequal to themselves. Q.E.D. P.S. Oh my god, did I just do a USAMO problem? I didn't even qualify for AIME!! But they're much harder nowadays. Also, by = I meant congruence, sorry, and I obviously used the parentheses for order. I think, however, that it's a good solution. Edit: If there is something flawed with my solution, or if it is correct, tell me. If it is correct, I'd love to add this brief solution to the AoPS wiki, but I don't know latex.
20.05.2010 00:40
Oh, there is a flaw. A number that is zmod z-na isn't necessarily equal to z-na.
24.05.2010 02:51
funny. A very similar problem was just used this year for the University of Illinois Undergrad Contest. It was pretty much this problem plus also the case of $P(a)=b$ and $P(b)=a$.
21.10.2011 12:12
Suppose that $a < b < c$. Then $|P(a) - P(c)| = |b-a|< |a-c|$, a contradiction. Next, suppose that $b < a < c$. Then $|P(b) - P(c)| = |c - a| < |c-b|$, also a contradiction. Note that these are both contradictions because $|a-c|$ divides $|P(a) - P(c)|$ and $|c-b|$ divides $|P(b) - P(c)|$.
30.10.2013 13:06
Using the well-known fact that $(a-b)\mid P(a)-P(b)$ we get $\frac{P(a)-P(b)}{a-b}=\frac{b-c}{a-b}=k_1$ $\frac{P(b)-P(c)}{b-c}=\frac{c-a}{b-c}=k_2$ $\frac{P(c)-P(a)}{c-a}=\frac{a-b}{c-a}=k_3$ where the $k_i$ are integral. Multiplying the first and last equations we have that \[\left(\frac{P(a)-P(b)}{a-b}\right)\left(\frac{P(c)-P(a)}{c-a}\right)=\frac{b-c}{c-a}=k_1k_3.\] But $\frac{b-c}{c-a}=\frac{1}{k_2}$, so the only way for $k_2$ to be an integer is if $|k_2|=1$. Similarly we get that $|k_1|=|k_3|=1$. If one of $k_1,k_2,k_3$ is -1, WLOG say $k_1$, then $\tfrac{b-c}{a-b}=-1\Leftrightarrow{b-c=-a+b}\Leftrightarrow{a=c}$, contradiction. Thus, $k_1,k_2,k_3$ are all equal to 1, and plugging these in it follows that $2a=b-c$, $2b=c-a$ and $2c=a-b$. Solving this system yields $a=b=c=0$, but $a,b,c$ are distinct integers by definition, a contradiction.
05.11.2013 21:12
These conditions imply that [a-b]<=[b-c]<=[c-a]<=[a-b],where [a]=modulus of a, so equality holds everywhere. Thus the fact that a,b,c are distinct implies (a-b)=(b-c)=(c-a).Solving we get a=b=c. Contradiction!
01.07.2014 19:50
Agr_94_Math wrote: $ a,b,c \in \mathbb{Z}$, and $ a,b,c$ are distinct. Since we have $ P[\mathbb{Z}]$, suppose we have by the given conditions to be exisitng such that $ a-b | b-c$ $ b-c | c-a$ $ c-a | a-b$. As we are dealing over integers, $ 2b\ge c+a$ $ 2c\ge a+b$ $ 2a\ge b+c$ THis however implies equaltiy holds everywhere and therefore contradiction. How did he immediately arrive at the conclusion: $ a-b | b-c$ $ b-c | c-a$ $ c-a | a-b$
01.07.2014 20:04
It's well-known that $a-b|P(a)-P(b)$ for integers $a$ and $b$ and a polynomial $P$ with integral coefficients. To see why, write out the expression $P(a)-P(b)$ and then refactor it so you get a lot of terms of the form $a^k-b^k$ for some $k$. Then $a-b$ divides all of these terms, and $P(a)-P(b)$ is a linear combination of terms of this form, so $a-b|P(a)-P(b)$.
01.07.2014 20:07
Here's what I did: Since $\frac{a-b}{b-c}, \frac{b-c}{c-a}, \frac{c-a}{a-b}$ are all integers and their product is equal to $1$, all three of them are each either $1$ or $-1$. At least one of the fractions equals 1, so WLOG $\frac{a-b}{b-c}=1$. THen either both of the remaining fractions equal 1 or both equal -1, so we examine the two cases. Both cases give us that $a=b=c$, contradiction.
01.07.2014 20:37
Okay I guess I wasn't thinking. I forgot that $P(a)=b$ and $P(b)=c$.
09.10.2015 04:29
Here is a solution I wrote up a while ago: Lemma 1: If $P(x)$ is a polynomial with integer coefficients then $a-b|P(a)-P(b)$ where $a,b$ are integers. Proof: Let $P(x)=a_n*x^n+a_{n-1}x^{n-1}...+a_1x+a_0$. We have $P(a)=a_n*a^n+a_{n-1}a^{n-1}...+a_1a+a_0$ and $P(b)=a_nb^n+a_{n-1}b^{n-1}...a_1b+a_0$. So $P(a)-P(b)=(a^n-b^n)a_n+(a^{n-1}-b^{n-1})a_{n-1}+...+(a-b)a_1$. Notice that $a^k-b^k=(a-b)(a^{k-1}+a^{k-2}b+...b^{k-1})$ so it is easy to see $a-b|P(a)-P(b)$. We will prove this by contradiction. By Lemma 1 we have $a-b|P(a)-P(b)$, $b-c|P(b)-P(c)$, and $c-a|P(c)-P(a)$. We know what $P(a), P(b),$ and $P(c)$ are as they were given in the problem so we substitute them in. Let $\frac{b-c}{a-b}=k$, $\frac{c-a}{b-c}=m$, and $\frac{a-b}{c-a}=t$ where $k,m,t$ are integers. Note that $kmt=1$ and because $k,m,t$ are integers it follows either all of them are $1$ or two of them are $-1$ and the other is $1$. Let's split this into two cases: Case 1: $k=m=t=1$. From here we have $b-c=a-b$, $c-a=b-c$, and $a-b=c-a$. This gives us that $a=b=c$ but the problem said $a,b,c$ are distinct so this case is ruled out. Case 2: WLOG let $k=m=-1$ and $t=1$. This means that $a=b=c$ again, meaning that it is impossible for $P(a)=b$, $P(b)=c$, and $P(c)=a$.
09.06.2018 04:21
18.09.2018 21:14
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$
18.08.2019 08:51
A bit different finishing....... Like others did, I also used the well known fact that $x-y|P(x)-P(y)$. So, by this fact we get $$a-b|b-c$$$$b-c|c-a$$$$c-a|a-b$$. Now we will consider this into two cases when $a-b=b-c$, $b-c=c-a$ and and the other case will be when $a-b<b-c$, $b-c<c-a$ and $c-a<a-b$. So, by adding all the inequalities we get $a+b+c<a+b+c$ which is impossible. Now we will consider when $a-b=b-c$, $b-c=c-a$ and $c-a=a-b$. From this we get $a=b=c$, which is clearly not possible, as the question says that $a,b,c$ are distinct integers. Hence, not possible.
18.08.2019 09:12
Indian MO 1986.
03.02.2020 03:37
Let $P(x) = d_nx^n+d_{n-1}x^{n-1}+...+d_0$. We have that $$P(m)-P(n) = d_n(m^n-n^n)+d_{n-1}(m^{n-1}-n^{n-1})+...+d_1(m-n)$$, which is clearly divisible by $m-n$. Hence, $$(a-b)|(b-c)$$$$(b-c)|(c-a)$$$$(c-a)|(a-b).$$Therefore, $|a-b|=|b-c|=|c-a|$. Letting $x=a-b$, $y=b-c$, and $x+y=c-a$, we have that $|x|=|y|=|x+y|$. $x=-y \implies a=c$, so we know that $x=y$. In other words, $|y|=|2y| \implies y = 0$. If $y=0$, then $b=c$, which is impossible. $\blacksquare$
03.02.2020 04:12
I don't see the point of commenting on an ancient post that is well-known... especially when the solution that you just posted is basically the same as everyone else's
04.06.2020 19:29
@above well writing your solution up helps you become better at math because you can reflect on your solution. my first ever USAMO solve
05.06.2020 01:11
My solution is basically @sayantanchakraborty's, but I feel like the explanation of mine is slightly more concise:
12.04.2021 21:40
31.08.2021 19:19
15.10.2021 20:29
FTSOC,assume that we can have $P(a)=b,P(b)=c,P(c)=a$ simultaneously. Then $$a-c|P(P(c))-P(P(a))=a-b$$and $$a-b|P(P(b))-P(P(a))=a-c$$implying $b=c$, contradiction.
21.11.2022 16:08
13.04.2023 07:26
Agr_94_Math wrote: $ a,b,c \in \mathbb{Z}$, and $ a,b,c$ are distinct. Since we have $ P[\mathbb{Z}]$, suppose we have by the given conditions to be exisitng such that $ a-b | b-c$ $ b-c | c-a$ $ c-a | a-b$. As we are dealing over integers, $ 2b\ge c+a$ $ 2c\ge a+b$ $ 2a\ge b+c$ THis however implies equaltiy holds everywhere and therefore contradiction. hmm, I don't understand how you got to a-b|b-c. Can someone explain the omitted part?
13.04.2023 09:35
huashiliao2020 wrote: hmm, I don't understand how you got to a-b|b-c. Can someone explain the omitted part? $a-b|P(a)-P(b)=b-c$
11.08.2023 01:12
$a-b|P(a)-P(b)$ --> $a-b|b-c$ Similarly, $b-c|c-a$, $c-a|a-b$ So this means $|a-b|=|b-c|=|c-a|$ WLOG $a<b<c$ $b-a=c-b=c-a$ $a=b$ (contradiction)