Difference between revisions of "1994 AIME Problems/Problem 7"
m |
m |
||
| (20 intermediate revisions by 8 users not shown) | |||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | For certain ordered pairs <math>(a,b)\,</math> of real | + | For certain ordered pairs <math>(a,b)\,</math> of [[real number]]s, the system of equations |
<center><math>ax+by=1\,</math></center> | <center><math>ax+by=1\,</math></center> | ||
<center><math>x^2+y^2=50\,</math></center> | <center><math>x^2+y^2=50\,</math></center> | ||
has at least one solution, and each solution is an ordered pair <math>(x,y)\,</math> of integers. How many such ordered pairs <math>(a,b)\,</math> are there? | has at least one solution, and each solution is an ordered pair <math>(x,y)\,</math> of integers. How many such ordered pairs <math>(a,b)\,</math> are there? | ||
| − | == Solution == | + | ==Solution== |
| − | {{ | + | |
| + | The equation <math>x^2+y^2=50</math> is that of a circle of radius <math>\sqrt{50}</math>, centered at the origin. By testing integers until the left side becomes too big, we see that the lattice points on this circle are <math>(\pm1,\pm7)</math>, <math>(\pm5,\pm5)</math>, and <math>(\pm7,\pm1)</math> where the signs are all independent of each other, for a total of <math>3\cdot 2\cdot 2=12</math> lattice points. They are indicated by the blue dots below. | ||
| + | |||
| + | <asy> size(150); draw(circle((0,0),sqrt(50))); | ||
| + | |||
| + | draw((1,7)--(-1,-7),red); draw((7,1)--(5,-5), green); | ||
| + | |||
| + | dot((0,0)); | ||
| + | |||
| + | dot((1,7),blue); dot((1,-7),blue); dot((-1,7),blue); dot((-1,-7),blue); | ||
| + | |||
| + | dot((5,5),blue); dot((5,-5),blue); dot((-5,5),blue); dot((-5,-5),blue); | ||
| + | |||
| + | dot((7,1),blue); dot((7,-1),blue); dot((-7,1),blue); dot((-7,-1),blue); </asy> | ||
| + | |||
| + | Since <math>(x,y)=(0,0)</math> yields <math>a\cdot 0+b\cdot 0=0 \neq 1</math>, we know that <math>ax+by=1</math> is the equation of a line that does not pass through the origin. So, we are looking for the number of lines which pass through at least one of the <math>12</math> lattice points on the circle, but do not pass through the origin or through any non-lattice point on the circle. An example is the green line above. It is straightforward to show that a line passes through the origin precisely when there exist two opposite points <math>(p,q)</math> and <math>(-p,-q)</math> through which it passes. And example is the red line above. | ||
| + | |||
| + | There are <math>\binom{12}{2}=66</math> ways to pick two distinct lattice points, and subsequently <math>66</math> distinct lines which pass through two distinct lattice points on the circle. Then we subtract the lines which pass through the origin by noting that the lattice points on the circle can be grouped into opposite pairs <math>(p,q)</math> and <math>(-p,-q)</math>, for a total of <math>\frac{12}{2}=6</math> lines. Finally, we add the <math>12</math> unique tangent lines to the circle at each of the lattice points. | ||
| + | |||
| + | Therefore, our final count of distinct lines which pass through one or two of the lattice points on the circle, but do not pass through the origin, is<cmath>66-6+12=\boxed{72}.</cmath> | ||
== See also == | == See also == | ||
{{AIME box|year=1994|num-b=6|num-a=8}} | {{AIME box|year=1994|num-b=6|num-a=8}} | ||
| + | |||
| + | [[Category:Intermediate Combinatorics Problems]] | ||
| + | {{MAA Notice}} | ||
Latest revision as of 18:51, 8 January 2024
Problem
For certain ordered pairs 
of real numbers, the system of equations
has at least one solution, and each solution is an ordered pair 
of integers. How many such ordered pairs are there?
Solution
The equation 
is that of a circle of radius 
, centered at the origin. By testing integers until the left side becomes too big, we see that the lattice points on this circle are 
, 
, and 
where the signs are all independent of each other, for a total of 
lattice points. They are indicated by the blue dots below.
![[asy] size(150); draw(circle((0,0),sqrt(50))); draw((1,7)--(-1,-7),red); draw((7,1)--(5,-5), green); dot((0,0)); dot((1,7),blue); dot((1,-7),blue); dot((-1,7),blue); dot((-1,-7),blue); dot((5,5),blue); dot((5,-5),blue); dot((-5,5),blue); dot((-5,-5),blue); dot((7,1),blue); dot((7,-1),blue); dot((-7,1),blue); dot((-7,-1),blue); [/asy]](http://latex.artofproblemsolving.com/d/9/c/d9caa9b19e9237090cb4dc7341af417743e2bdd5.png)
Since 
yields 
, we know that 
is the equation of a line that does not pass through the origin. So, we are looking for the number of lines which pass through at least one of the 
lattice points on the circle, but do not pass through the origin or through any non-lattice point on the circle. An example is the green line above. It is straightforward to show that a line passes through the origin precisely when there exist two opposite points 
and 
through which it passes. And example is the red line above.
There are 
ways to pick two distinct lattice points, and subsequently 
distinct lines which pass through two distinct lattice points on the circle. Then we subtract the lines which pass through the origin by noting that the lattice points on the circle can be grouped into opposite pairs and , for a total of 
lines. Finally, we add the unique tangent lines to the circle at each of the lattice points.
Therefore, our final count of distinct lines which pass through one or two of the lattice points on the circle, but do not pass through the origin, is![\[66-6+12=\boxed{72}.\]](http://latex.artofproblemsolving.com/e/5/1/e515d3430a68f06f5255a181da6d02b223547584.png)
See also
| 1994 AIME (Problems • Answer Key • Resources) | ||
| Preceded by Problem 6 |
Followed by Problem 8 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
