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

(→‎Solution)
(→‎Solution)
 
(One intermediate revision by one other user not shown)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
−
If we let the two squares be <math>a^2 - b^2 = x</math>, then by difference of squares we have <math>(a-b)(a+b) = x</math>. Notice that <math>a-b</math> and <math>a+b</math> have the same [[parity|parities]]. This eliminates all numbers in the form of <math>4n+2</math>: when <math>x=2(2n+1)</math> is factored, one of the factors must be even, but not both, so its factors cannot have the same parity. However, one cannot be represented as the difference of squares.
+
Notice that all odd numbers can be obtained by using <math>(a+1)^2-a^2=2a+1,</math> where <math>a</math> is a nonnegative integer. All multiples of <math>4</math> can be obtained by using <math>(b+1)^2-(b-1)^2 = 4b</math>, where <math>b</math> is a positive integer. Numbers congruent to <math>2 \pmod 4</math> cannot be obtained because squares are <math> 0, 1 \pmod 4.</math> Thus, the answer is <math>500+250 = \boxed{750}.</math>
−
 
 
−
For the remaining <math>\boxed{749}</math> numbers with the exception of 1, we can describe specific squares which fit the conditions:
 
−
*For all odd <math>x = 2n+1</math>, <math>(n+1)^2 - (n^2) = x</math>.
 
−
*For all <math>x = 4n</math>, <math>(n+1)^2 - (n-1)^2 = x</math>.
 
  
 
== See also ==
 
== See also ==

Latest revision as of 14:52, 2 March 2020

Problem

How many of the integers between 1 and 1000, inclusive, can be expressed as the difference of the squares of two nonnegative integers?

Solution

Notice that all odd numbers can be obtained by using $(a+1)^2-a^2=2a+1,$ where $a$ is a nonnegative integer. All multiples of $4$ can be obtained by using $(b+1)^2-(b-1)^2 = 4b$, where $b$ is a positive integer. Numbers congruent to $2 \pmod 4$ cannot be obtained because squares are $0, 1 \pmod 4.$ Thus, the answer is $500+250 = \boxed{750}.$

See also

1997 AIME (Problems • Answer Key • Resources)
Preceded by
First Question 		Followed by
Problem 2
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=1997_AIME_Problems/Problem_1&oldid=118662"