Difference between revisions of "2014 USAMO Problems/Problem 3"
(Added elliptic curve solution) |
(→Solution 2 (Function Theory)) |
||
(2 intermediate revisions by the same user not shown) | |||
Line 2: | Line 2: | ||
Prove that there exists an infinite set of points <cmath>\ldots,\,\,\,\,P_{-3},\,\,\,\,P_{-2},\,\,\,\,P_{-1},\,\,\,\,P_0,\,\,\,\,P_1,\,\,\,\,P_2,\,\,\,\,P_3,\,\,\,\,\ldots</cmath> in the plane with the following property: For any three distinct integers <math>a,b,</math> and <math>c</math>, points <math>P_a</math>, <math>P_b</math>, and <math>P_c</math> are collinear if and only if <math>a+b+c=2014</math>. | Prove that there exists an infinite set of points <cmath>\ldots,\,\,\,\,P_{-3},\,\,\,\,P_{-2},\,\,\,\,P_{-1},\,\,\,\,P_0,\,\,\,\,P_1,\,\,\,\,P_2,\,\,\,\,P_3,\,\,\,\,\ldots</cmath> in the plane with the following property: For any three distinct integers <math>a,b,</math> and <math>c</math>, points <math>P_a</math>, <math>P_b</math>, and <math>P_c</math> are collinear if and only if <math>a+b+c=2014</math>. | ||
− | ==Solution== | + | ==Solution (Group Theory)== |
Consider an elliptic curve with a generator <math>g</math>, such that <math>g</math> is not a root of <math>0</math>. By repeatedly adding <math>g</math> to itself under the standard group operation, with can build <math>g, 2g, 3g, \ldots</math> as well as <math>-g, -2g, -3g, \ldots</math>. If we let <cmath>P_k = (3k-2014)g</cmath> then we can observe that collinearity between <math>P_a</math>, <math>P_b</math>, and <math>P_c</math> occurs only if <math>P_a + P_b + P_c = 0</math> (by definition of the group operation), which is equivalent to <math>(3a-2014)g + (3b-2014)g + (3c-2014)g = (3a+3b+3c-3*2014)g = 0</math>, or <math>3a + 3b + 3c = 3*2014</math>, or <math>a + b + c = 2014</math>. We know that all these points <math>P_k</math> exist because <math>3k-2014</math> is never 0 for integer <math>k</math>, so that none of these points need to be point at infinity (the identity element of the group). | Consider an elliptic curve with a generator <math>g</math>, such that <math>g</math> is not a root of <math>0</math>. By repeatedly adding <math>g</math> to itself under the standard group operation, with can build <math>g, 2g, 3g, \ldots</math> as well as <math>-g, -2g, -3g, \ldots</math>. If we let <cmath>P_k = (3k-2014)g</cmath> then we can observe that collinearity between <math>P_a</math>, <math>P_b</math>, and <math>P_c</math> occurs only if <math>P_a + P_b + P_c = 0</math> (by definition of the group operation), which is equivalent to <math>(3a-2014)g + (3b-2014)g + (3c-2014)g = (3a+3b+3c-3*2014)g = 0</math>, or <math>3a + 3b + 3c = 3*2014</math>, or <math>a + b + c = 2014</math>. We know that all these points <math>P_k</math> exist because <math>3k-2014</math> is never 0 for integer <math>k</math>, so that none of these points need to be point at infinity (the identity element of the group). | ||
+ | |||
+ | ==Solution 2 (Function Theory)== | ||
+ | Consider letting <math>P_x</math> be the point <math>(x, f(x))</math>, where <math>f(x) = x^3 - 2014x^2</math>. Then if three points <math>P_a, P_b, P_c</math> are on the same line <math>y = mx + p</math>, they must be the solutions to the equation <math>x^3 - 2014x^2 = mx + p</math> (i.e. the intersection of <math>f</math> and the line). By Vieta's Formulas, the sum of the roots to this equation is 2014. Because each value of x corresponds to a different one of a, b, and c by definition of <math>P_x</math>, <math>a + b + c = 2014</math>. Conversely, if <math>a + b + c = 2014</math>, they must be the solutions to <math>(x-a)(x-b)(x-c) = x^3 - 2014x^2 - mx - p = 0</math> for some real <math>m</math> and <math>p</math>. Clearly, then, <math>P_a, P_b, P_c</math> must all lie on the line <math>y = mx + p</math>. Hence, our setting <math>P_x = f(x)</math> produces a valid infinite set of points. | ||
+ | |||
+ | ''Note: We could have let <math>f(x) = ax^3 - 2014ax^2 + bx + c</math>, where a, b, and c are arbitrary constants. (a is nonzero.)'' |
Latest revision as of 19:09, 1 May 2014
Problem
Prove that there exists an infinite set of points in the plane with the following property: For any three distinct integers
and
, points
,
, and
are collinear if and only if
.
Solution (Group Theory)
Consider an elliptic curve with a generator , such that
is not a root of
. By repeatedly adding
to itself under the standard group operation, with can build
as well as
. If we let
then we can observe that collinearity between
,
, and
occurs only if
(by definition of the group operation), which is equivalent to
, or
, or
. We know that all these points
exist because
is never 0 for integer
, so that none of these points need to be point at infinity (the identity element of the group).
Solution 2 (Function Theory)
Consider letting be the point
, where
. Then if three points
are on the same line
, they must be the solutions to the equation
(i.e. the intersection of
and the line). By Vieta's Formulas, the sum of the roots to this equation is 2014. Because each value of x corresponds to a different one of a, b, and c by definition of
,
. Conversely, if
, they must be the solutions to
for some real
and
. Clearly, then,
must all lie on the line
. Hence, our setting
produces a valid infinite set of points.
Note: We could have let , where a, b, and c are arbitrary constants. (a is nonzero.)