Difference between revisions of "1974 USAMO Problems/Problem 1"
(→Problem) |
(→Solution 1b) |
||
Line 19: | Line 19: | ||
===Solution 1b=== | ===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, | + | 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== | ==Solution 2== |
Revision as of 15:37, 31 August 2014
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.
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.