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 "1994 AIME Problems/Problem 7"

(→‎Solution (the original was kinda wrong) (the original was not wrong))
m
 
(8 intermediate revisions by 3 users not shown)
Line 5: Line 5:
 
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 (the original was kinda wrong) (the original was not wrong) ==
+
==Solution==
−
disproving the "proof" below:
 
−
To be honest, I also thought that there would be infinite solutions for this problem when I first read it, just like the "proof" below. However, if there is one solution, then the line will touch the circle at one point, and this will be a tangent line at a lattice point on the circle. There is only one tangent line for each lattice point on the circle, and there are 12 lattice points on the circle. If there are two solutions, then the line will intersect the circle at two points, and both of these points must have integer coordinates, so we have to pick two points from our 12 lattice points to connect. Continue as the solution after the "proof" below.
 
−
 
 
−
 
 
−
bro whoever made this problem must've been smoking the best weed I've ever heard of because, even though the solution says there are 72 solutions, there are actually infinite. proof here:
 
−
 
 
−
ok, so we know that, for the second equation alone, (x, y) = (5, 5) is a solution. if we plug this into the first equation, we get 5a+5b=1. then we simplify to get a+b=1/5. As we can see, this equation by itself obviously has infinite solutions, and, just to confirm my point, i put 100 solutions (way more than 72) below right here, given there are more than 72:
 
−
 
 
−
(x, y) = (5, 5) in every solution, these are the solutions for (a, b):
 
−
 
 
−
(0.00, 0.20)
 
−
(0.01, 0.19)
 
−
(0.02, 0.18)
 
−
(0.03, 0.17)
 
−
(0.04, 0.16)
 
−
(0.05, 0.15)
 
−
(0.06, 0.14)
 
−
(0.07, 0.13)
 
−
(0.08, 0.12)
 
−
(0.09, 0.11)
 
−
(0.10, 0.10)
 
−
(0.11, 0.09)
 
−
(0.12, 0.08)
 
−
(0.13, 0.07)
 
−
(0.14, 0.06)
 
−
(0.15, 0.05)
 
−
(0.16, 0.04)
 
−
(0.17, 0.03)
 
−
(0.18, 0.02)
 
−
(0.19, 0.01)
 
−
(0.20, 0.00)
 
−
(0.21, -0.01)
 
−
(0.22, -0.02)
 
−
(0.23, -0.03)
 
−
(0.24, -0.04)
 
−
(0.25, -0.05)
 
−
(0.26, -0.06)
 
−
(0.27, -0.07)
 
−
(0.28, -0.08)
 
−
(0.29, -0.09)
 
−
(0.30, -0.10)
 
−
(0.31, -0.11)
 
−
(0.32, -0.12)
 
−
(0.33, -0.13)
 
−
(0.34, -0.14)
 
−
(0.35, -0.15)
 
−
(0.36, -0.16)
 
−
(0.37, -0.17)
 
−
(0.38, -0.18)
 
−
(0.39, -0.19)
 
−
(0.40, -0.20)
 
−
(0.41, -0.21)
 
−
(0.42, -0.22)
 
−
(0.43, -0.23)
 
−
(0.44, -0.24)
 
−
(0.45, -0.25)
 
−
(0.46, -0.26)
 
−
(0.47, -0.27)
 
−
(0.48, -0.28)
 
−
(0.49, -0.29)
 
−
(0.50, -0.30)
 
−
(0.51, -0.31)
 
−
(0.52, -0.32)
 
−
(0.53, -0.33)
 
−
(0.54, -0.34)
 
−
(0.55, -0.35)
 
−
(0.56, -0.36)
 
−
(0.57, -0.37)
 
−
(0.58, -0.38)
 
−
(0.59, -0.39)
 
−
(0.60, -0.40)
 
−
(0.61, -0.41)
 
−
(0.62, -0.42)
 
−
(0.63, -0.43)
 
−
(0.64, -0.44)
 
−
(0.65, -0.45)
 
−
(0.66, -0.46)
 
−
(0.67, -0.47)
 
−
(0.68, -0.48)
 
−
(0.69, -0.49)
 
−
(0.70, -0.50)
 
−
(0.71, -0.51)
 
−
(0.72, -0.52)
 
−
(0.73, -0.53)
 
−
(0.74, -0.54)
 
−
(0.75, -0.55)
 
−
(0.76, -0.56)
 
−
(0.77, -0.57)
 
−
(0.78, -0.58)
 
−
(0.79, -0.59)
 
−
(0.80, -0.60)
 
−
(0.81, -0.61)
 
−
(0.82, -0.62)
 
−
(0.83, -0.63)
 
−
(0.84, -0.64)
 
−
(0.85, -0.65)
 
−
(0.86, -0.66)
 
−
(0.87, -0.67)
 
−
(0.88, -0.68)
 
−
(0.89, -0.69)
 
−
(0.90, -0.70)
 
−
(0.91, -0.71)
 
−
(0.92, -0.72)
 
−
(0.93, -0.73)
 
−
(0.94, -0.74)
 
−
(0.95, -0.75)
 
−
(0.96, -0.76)
 
−
(0.97, -0.77)
 
−
(0.98, -0.78)
 
−
(0.99, -0.79)
 
−
 
 
−
 
 
  
 
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.
 
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]
+
<asy> size(150); draw(circle((0,0),sqrt(50)));
−
size(150);
 
−
draw(circle((0,0),sqrt(50)));
 
  
−
draw((1,7)--(-1,-7),red);
+
draw((1,7)--(-1,-7),red); draw((7,1)--(5,-5), green);
−
draw((7,1)--(5,-5), green);
 
  
 
dot((0,0));
 
dot((0,0));
  
−
dot((1,7),blue);
+
dot((1,7),blue); dot((1,-7),blue); dot((-1,7),blue); 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((-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); dot((-7,-1),blue); </asy>
−
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.
 
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.

Latest revision as of 18:51, 8 January 2024

Problem

For certain ordered pairs $(a,b)\,$ of real numbers, the system of equations

$ax+by=1\,$
$x^2+y^2=50\,$

has at least one solution, and each solution is an ordered pair $(x,y)\,$ of integers. How many such ordered pairs $(a,b)\,$ are there?

Solution

The equation $x^2+y^2=50$ is that of a circle of radius $\sqrt{50}$, centered at the origin. By testing integers until the left side becomes too big, we see that the lattice points on this circle are $(\pm1,\pm7)$, $(\pm5,\pm5)$, and $(\pm7,\pm1)$ where the signs are all independent of each other, for a total of $3\cdot 2\cdot 2=12$ 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 $(x,y)=(0,0)$ yields $a\cdot 0+b\cdot 0=0 \neq 1$, we know that $ax+by=1$ 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 $12$ 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 $(p,q)$ and $(-p,-q)$ through which it passes. And example is the red line above.

There are $\binom{12}{2}=66$ ways to pick two distinct lattice points, and subsequently $66$ 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 $(p,q)$ and $(-p,-q)$, for a total of $\frac{12}{2}=6$ lines. Finally, we add the $12$ 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}.\]

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1994_AIME_Problems/Problem_7&oldid=210227"