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 "2013 AIME II Problems/Problem 6"

(→‎Solution 4)
m (→‎Solution 4)
Line 20: Line 20:
  
 
==Solution 4==
 
==Solution 4==
−
We want to find the least <math>N \in \mathbb{N}</math> such that <math>\exists m \in \mathbb{N}</math> where <math>m^2 < 1000N, 1000N + 1000 < (m+1)^2</math>.
+
We want to find the least <math>N \in \mathbb{N}</math> such that <math>\exists m \in \mathbb{N}</math> where <math>m^2 + 1 \leq 1000N, 1000N + 1000 \leq (m+1)^2</math>.
  
  
 
Combining the two inequalities, we have,
 
Combining the two inequalities, we have,
  
 +
<math>(m+1)^2 \geq m^2 + 1001</math>,
  
−
<math>(m+1)^2 > m^2 + 1000</math>
+
<math>m \geq 500</math>.
  
  
−
<math>2m + 1 > 1000</math>
+
Let <math>m = k + 500</math>, where <math>k \in \mathbb{W}</math>, then the inequalities become,
  
 +
<math>N \geq \frac{(k+500)^2 + 1}{1000} = \frac{k^2 + 1}{1000} + k + 250</math>, and
  
−
<math>m > 499.5</math>
+
<math>N \leq \frac{(k+501)^2}{1000} - 1 = \frac{(k+1)^2}{1000} + k + 250.</math>
  
  
−
Since <math>m \in \mathbb{N}, m \geq 500,</math>
+
For <math>k=31</math>, one can verify that <math>N = 282</math> is the unique integer satisfying the inequalities.
  
 +
For <math>k \leq 30</math>, <math>k + 250 < \frac{k^2 + 1}{1000} + k + 250 \leq N</math> <math>\leq \frac{(k+1)^2}{1000} + k + 250 \leq \frac{(30+1)^2}{1000} + k + 250 < k + 251</math>, a contradiction.
  
−
Let <math>m = k + 500</math>, where <math>k \in \mathbb{W}</math>.
+
Note <math>k \geq 32</math> leads to larger <math>N</math>.
  
 +
Hence, the answer is <math>\boxed{282}</math>.
  
−
Then, the inequalities become,
+
\yuxiaomatt
−
 
 
−
 
 
−
<math>N > \frac{(k+500)^2}{1000} = \frac{k^2}{1000} + k + 250</math>, and
 
−
 
 
−
 
 
−
<math>N < \frac{(k+501)^2}{1000} - 1 = \frac{(k+1)^2}{1000} + k + 250.</math>
 
−
 
 
−
 
 
−
Since we want to minimize <math>N</math>, we want the minimum <math>k</math> such that there exists a
 
−
positive integer between <math>\frac{k^2}{1000} + k + 250</math> and <math>\frac{(k+1)^2}{1000} + k + 250.</math> Since <math>k + 250 \in \mathbb{N}</math>, we need the minimum <math>k</math> such that there
 
−
exists a positive integer between <math>\frac{k^2}{1000}</math> and <math>\frac{(k+1)^2}{1000}</math>. It is now trivial to see that the minimum <math>k</math> is <math>31</math>, since <math>31^2 = 961</math>, <math>32^2 = 1024</math>. This produces <math>N = \boxed{282}</math> as the answer.
 
  
 
==See Also==
 
==See Also==

Revision as of 14:20, 21 July 2021

Problem 6

Find the least positive integer $N$ such that the set of $1000$ consecutive integers beginning with $1000\cdot N$ contains no square of an integer.

Solutions

Solution 1

The difference between consecutive integral squares must be greater than 1000. $(x+1)^2-x^2\geq1000$, so $x\geq\frac{999}{2}\implies x\geq500$. $x=500$ does not work, so $x>500$. Let $n=x-500$. The sum of the square of $n$ and a number a little over 1000 must result in a new perfect square. By inspection, $n^2$ should end in a number close to but less than 1000 such that there exists $1000N$ within the difference of the two squares. Examine when $n^2=1000$. Then, $n=10\sqrt{10}$. One example way to estimate $\sqrt{10}$ follows. 

$3^2=9$, so $10=(x+3)^2=x^2+6x+9$. $x^2$ is small, so $10=6x+9$. $x=1/6\implies \sqrt{10}\approx 19/6$. This is 3.16.

Then, $n\approx 31.6$. $n^2<1000$, so $n$ could be $31$. Add 500 to get the first square and 501 to get the second. Then, the two integral squares are $531^2$ and $532^2$. Checking, $531^2=281961$ and $532^2=283024$. $282,000$ straddles the two squares, which have a difference of 1063. The difference has been minimized, so $N$ is minimized $N=282000\implies\boxed{282}$

~BJHHar

Solution 2

Let us first observe the difference between $x^2$ and $(x+1)^2$, for any arbitrary $x\ge 0$. $(x+1)^2-x^2=2x+1$. So that means for every $x\ge 0$, the difference between that square and the next square have a difference of $2x+1$. Now, we need to find an $x$ such that $2x+1\ge 1000$. Solving gives $x\ge \frac{999}{2}$, so $x\ge 500$. Now we need to find what range of numbers has to be square-free: $\overline{N000}\rightarrow \overline{N999}$ have to all be square-free. Let us first plug in a few values of $x$ to see if we can figure anything out. $x=500$, $x^2=250000$, and $(x+1)^2=251001$. Notice that this does not fit the criteria, because $250000$ is a square, whereas $\overline{N000}$ cannot be a square. This means, we must find a square, such that the last $3$ digits are close to $1000$, but not there, such as $961$ or $974$. Now, the best we can do is to keep on listing squares until we hit one that fits. We do not need to solve for each square: remember that the difference between consecutive squares are $2x+1$, so all we need to do is addition. After making a list, we find that $531^2=281961$, while $532^2=283024$. It skipped $282000$, so our answer is $\boxed{282}$.

Solution 3

Let $x$ be the number being squared. Based on the reasoning above, we know that $N$ must be at least $250$, so $x$ has to be at least $500$. Let $k$ be $x-500$. We can write $x^2$ as $(500+k)^2$, or $250000+1000k+k^2$. We can disregard $250000$ and $1000k$, since they won't affect the last three digits, which determines if there are any squares between $\overline{N000}\rightarrow \overline{N999}$. So we must find a square, $k^2$, such that it is under $1000$, but the next square is over $1000$. We find that $k=31$ gives $k^2=961$, and so $(k+1)^2=32^2=1024$. We can be sure that this skips a thousand because the $1000k$ increments it up $1000$ each time. Now we can solve for $x$: $(500+31)^2=281961$, while $(500+32)^2=283024$. We skipped $282000$, so the answer is $\boxed{282}$.

Solution 4

We want to find the least $N \in \mathbb{N}$ such that $\exists m \in \mathbb{N}$ where $m^2 + 1 \leq 1000N, 1000N + 1000 \leq (m+1)^2$.


Combining the two inequalities, we have,

$(m+1)^2 \geq m^2 + 1001$,

$m \geq 500$.


Let $m = k + 500$, where $k \in \mathbb{W}$, then the inequalities become,

$N \geq \frac{(k+500)^2 + 1}{1000} = \frac{k^2 + 1}{1000} + k + 250$, and

$N \leq \frac{(k+501)^2}{1000} - 1 = \frac{(k+1)^2}{1000} + k + 250.$


For $k=31$, one can verify that $N = 282$ is the unique integer satisfying the inequalities.

For $k \leq 30$, $k + 250 < \frac{k^2 + 1}{1000} + k + 250 \leq N$ $\leq \frac{(k+1)^2}{1000} + k + 250 \leq \frac{(30+1)^2}{1000} + k + 250 < k + 251$, a contradiction.

Note $k \geq 32$ leads to larger $N$.

Hence, the answer is $\boxed{282}$.

\yuxiaomatt

See Also

Very similar to 2016 AMC 12 A Problem 25: https://artofproblemsolving.com/wiki/index.php/2016_AMC_12A_Problems/Problem_25

2013 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 5 		Followed by
Problem 7
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=2013_AIME_II_Problems/Problem_6&oldid=158832"