Difference between revisions of "2013 AIME II Problems/Problem 6"

Revision as of 13:37, 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.

, so .  is small, so . . 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 < 1000N, 1000N + 1000 < (m+1)^2$ .

Combining the two inequalities, we have,

$(m+1)^2 > m^2 + 1000$

$2m + 1 > 1000$

$m > 499.5$

Since $m \in \mathbb{N}, m \geq 500,$

Let $m = k + 500$ , where $k \in \mathbb{W}$ .

Then, the inequalities become,

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

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

Since we want to minimize $N$ , we want the minimum $k$ such that there exists a positive integer between $\frac{k^2}{1000} + k + 250$ and $\frac{(k+1)^2}{1000} + k + 250.$ Since $k + 250 \in \mathbb{N}$ , we need the minimum $k$ such that there exists a positive integer between $\frac{k^2}{1000}$ and $\frac{(k+1)^2}{1000}$ . It is now trivial to see that the minimum $k$ is $31$ , since $31^2 = 961$ , $32^2 = 1024$ . This produces $N = 282$ as the minimum possible.

@@ Line 21: / Line 21: @@
 ==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>.
+Combining the two inequalities, we have,
+<math>(m+1)^2 > m^2 + 1000</math>
+<math>2m + 1 > 1000</math>
+<math>m > 499.5</math>
+Since <math>m \in \mathbb{N}, m \geq 500,</math>
+Let <math>m = k + 500</math>, where <math>k \in \mathbb{W}</math>.
+Then, the inequalities become,
+<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 = 282</math> as the minimum possible.
 ==See Also==

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

Page

Toolbox

Search