Difference between revisions of "1974 USAMO Problems/Problem 1"
(→Solution 4) |
|||
Line 39: | Line 39: | ||
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. | 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}} | ||
Latest revision as of 20:30, 27 April 2020
Contents
Problem
Let ,
, and
denote three distinct integers, and let
denote a polynomial having all integral coefficients. Show that it is impossible that
,
, and
.
Hint
If is a polynomial with integral coefficients, then
(Why?)
Solution
It suffices to show that if are integers such that
,
, and
, then
.
We note that
so the quanitities
must be equal in absolute value. In fact, two of them, say
and
, must be equal. Then
so
, and
, so
,
, and
are equal, as desired.
Solution 1b
Let be the value
are equal to in absolute value. Assume
is nonzero. Then each of
is equal to
or
, so
where
is one of -3, -1, 1, or 3. In particular, neither
nor
is zero, contradiction. Hence,
, and
are equal, yielding a final contradiction of the existence of these variables.
In fact, this approach generalizes readily. Suppose that is an odd integer, and that there exist
distinct integers
such that
and
, for
. Then we have
so the differences are all equal in absolute value and thus equal to
or
for some integer
. Adding the differences (in the order they are written) gives
for some odd integer
, so
is nonzero and hence
. Thus, all the
are equal, a contradiction of their distinctness, so the sequence
cannot exist.
Solution 2
Consider the polynomial By using the facts that
and
, we find that
Thus, the polynomial
has a and b as roots, and we can write
for some polynomial
. Because
and
are monic polynomials with integral coefficients, their quotient,
, must also have integral coefficients, as can be demonstrated by simulating the long division. Thus,
, and hence
, must be divisible by
. But if
and
, then we must have, after rearranging terms and substitution, that
is divisible by
. Equivalently,
is divisible by
(after canceling the
which is clearly divisble by
). 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 . Let
Note that
Subtracting the second from the first, third from second, and first from third gives
By the RHS, note that
so
Similarly,
and
Hence,
so
Assume WLOG that
so
and
From the first equation, we get
and substituting this in the second gives
Hence,
, contradicting the uniqueness of
Solution 4
Assume that and
are distinct integers which satisfy the given conditions. Then we have
. Similarly
and
. Since the polynomial has integer coefficients, this implies that the polynomial
is
. But this is a contradiction since then
can only be true if
which contradicts the fact that
and
are distinct integers.
Solution 5
We get that . Thus, we can say that
, for non zero integers, not necesarily positive, k, j, and m. Multiplying these equations and canceling, we get that
=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
, 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
. But this implies that the distinct integer condition is not satisfied, and hence, this case is invalid. Thus, it is impossible.
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.