Difference between revisions of "1974 USAMO Problems/Problem 1"

Revision as of 15:30, 31 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 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, 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.

@@ Line 13: / Line 13: @@
 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, as desired. <math>\blacksquare</math>
 ==Solution 2==

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

Page

Toolbox

Search