1974 USAMO Problems/Problem 1
Contents
[hide]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.