Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2014 USAMO Problems/Problem 3"

(Added elliptic curve solution)
(→‎Solution)
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. 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.

Revision as of 18:05, 1 May 2014

Problem

Prove that there exists an infinite set of points \[\ldots,\,\,\,\,P_{-3},\,\,\,\,P_{-2},\,\,\,\,P_{-1},\,\,\,\,P_0,\,\,\,\,P_1,\,\,\,\,P_2,\,\,\,\,P_3,\,\,\,\,\ldots\] in the plane with the following property: For any three distinct integers $a,b,$ and $c$, points $P_a$, $P_b$, and $P_c$ are collinear if and only if $a+b+c=2014$.

Solution (Group Theory)

Consider an elliptic curve with a generator $g$, such that $g$ is not a root of $0$. By repeatedly adding $g$ to itself under the standard group operation, with can build $g, 2g, 3g, \ldots$ as well as $-g, -2g, -3g, \ldots$. If we let \[P_k = (3k-2014)g\] then we can observe that collinearity between $P_a$, $P_b$, and $P_c$ occurs only if $P_a + P_b + P_c = 0$ (by definition of the group operation), which is equivalent to $(3a-2014)g + (3b-2014)g + (3c-2014)g = (3a+3b+3c-3*2014)g = 0$, or $3a + 3b + 3c = 3*2014$, or $a + b + c = 2014$. We know that all these points $P_k$ exist because $3k-2014$ is never 0 for integer $k$, so that none of these points need to be point at infinity (the identity element of the group).

Solution 2 (Function Theory)

Consider letting $P_x$ be the point $(x, f(x))$, where $f(x) = x^3 - 2014x^2$. Then if three points $P_a, P_b, P_c$ are on the same line $y = mx + p$, they must be the solutions to the equation $x^3 - 2014x^2 = mx + p$ (i.e. intersection of $f$ 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 $P_x$, $a + b + c = 2014$. Conversely, if $a + b + c = 2014$, they must be the solutions to $(x-a)(x-b)(x-c) = x^3 - 2014x^2 - mx - p = 0$ for some real $m$ and $p$. Clearly, then, $P_a, P_b, P_c$ must all lie on the line $y = mx + p$. Hence, our setting $P_x = f(x)$ produces a valid infinite set of points.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_USAMO_Problems/Problem_3&oldid=61873"