Difference between revisions of "2002 AIME II Problems/Problem 8"
Fuzimiao2013 (talk | contribs) (→Solution) |
(→Solution 4) |
||
(5 intermediate revisions by 4 users not shown) | |||
Line 21: | Line 21: | ||
Hence the least positive integer <math>k</math> for which the equation <math>\left\lfloor\frac{2002}{n}\right\rfloor=k</math> has no integer solutions for <math>n</math> is <math>\boxed{049}</math>. | Hence the least positive integer <math>k</math> for which the equation <math>\left\lfloor\frac{2002}{n}\right\rfloor=k</math> has no integer solutions for <math>n</math> is <math>\boxed{049}</math>. | ||
+ | |||
+ | ====Note==== | ||
+ | |||
+ | After getting that <math>\left\lfloor\frac{2002}{45}\right\rfloor=44</math>, for ease of computation above, we can use the fact that <math>(40+k)(49-k)</math> varies solely based on <math>k^2</math> and checking these gives us that the pattern fails at <math>k=0</math> giving us <math>\boxed{049}</math> as the answer. | ||
+ | |||
+ | ~Dhillonr25 | ||
===Solution 2=== | ===Solution 2=== | ||
Line 30: | Line 36: | ||
Now note that in order for there to be no integer solutions to <math>n,</math> we must have <math>\left\lfloor \frac{2002}{k} \right\rfloor = \left\lfloor \frac{2002}{k+1} \right\rfloor.</math> We seek the smallest such <math>k.</math> A bit of experimentation yields that <math>k=49</math> is the smallest solution, as for <math>k=49,</math> it is true that <math>\left\lfloor \frac{2002}{49} \right\rfloor = \left\lfloor \frac{2002}{50} \right\rfloor = 40.</math> Furthermore, <math>k=49</math> is the smallest such case. (If unsure, we could check if the result holds for <math>k=48,</math> and as it turns out, it doesn't.) Therefore, the answer is <math>\boxed{049}.</math> | Now note that in order for there to be no integer solutions to <math>n,</math> we must have <math>\left\lfloor \frac{2002}{k} \right\rfloor = \left\lfloor \frac{2002}{k+1} \right\rfloor.</math> We seek the smallest such <math>k.</math> A bit of experimentation yields that <math>k=49</math> is the smallest solution, as for <math>k=49,</math> it is true that <math>\left\lfloor \frac{2002}{49} \right\rfloor = \left\lfloor \frac{2002}{50} \right\rfloor = 40.</math> Furthermore, <math>k=49</math> is the smallest such case. (If unsure, we could check if the result holds for <math>k=48,</math> and as it turns out, it doesn't.) Therefore, the answer is <math>\boxed{049}.</math> | ||
− | ==Solution 3== | + | ===Solution 3=== |
In this solution we use inductive reasoning and a lot of trial and error. Depending on how accurately you can estimate, the solution will come quicker or slower. | In this solution we use inductive reasoning and a lot of trial and error. Depending on how accurately you can estimate, the solution will come quicker or slower. | ||
− | Using values of k as 1, 2, 3, 4, and 5, we can find the corresponding values of n relatively easily. For k = 1, n is in the range [2002-1002]; for k = 2, n is the the range [1001-668], etc: 3, [667,501]; 4, [500-401]; 5, [400-334]. For any positive integer k, n is in a range of <math> | + | Using values of <math>k</math> as <math>1, 2, 3, 4,</math> and <math>5,</math> we can find the corresponding values of <math>n</math> relatively easily. For <math>k = 1</math>, <math>n</math> is in the range <math>[2002-1002]</math>; for <math>k = 2</math>, <math>n</math> is the the range <math>[1001-668]</math>, etc: <math>3, [667,501]; 4, [500-401]; 5, [400-334]</math>. For any positive integer <math>k, n</math> is in a range of <math>\left\lfloor \frac{2002}{k} \right\rfloor -\left\lceil \frac{2002}{k+1} \right\rceil</math>. |
− | Now we try testing k = 1002 to get a better understanding of what our solution will look like. Obviously, there will be no solution for n, but we are more interested in how the range will compute to. Using the formula we got above, the range will be 1-2. Testing any integer k from 1002-2000 will result in the same range. Also, notice that each and every one of them have no solution for n. Testing 1001 gives a range of 2-2, and 2002 gives 1-1. They each have a solution for n, and their range is only one value. Therefore, we can assume with relative safety that the integer k we want is the lowest integer that follows this equation | + | Now we try testing <math>k = 1002</math> to get a better understanding of what our solution will look like. Obviously, there will be no solution for <math>n</math>, but we are more interested in how the range will compute to. Using the formula we got above, the range will be <math>1-2</math>. Testing any integer <math>k</math> from <math>1002-2000</math> will result in the same range. Also, notice that each and every one of them have no solution for <math>n</math>. Testing <math>1001</math> gives a range of <math>2-2</math>, and <math>2002</math> gives <math>1-1</math>. They each have a solution for <math>n</math>, and their range is only one value. Therefore, we can assume with relative safety that the integer <math>k</math> we want is the lowest integer that follows this equation |
− | + | <cmath>\left\lfloor\frac{2002}{k}\right\rfloor + 1 = \left\lceil \frac{2002}{k+1}\right\rceil</cmath> | |
− | Now we can easily guess and check starting from k = 1. After a few tests it's not difficult to estimate a few jumps, and it took me only a few minutes to realize the answer was somewhere in the forties. Then it's just a matter of checking them until we get <math>\boxed{049}</math>. | + | Now we can easily guess and check starting from <math>k = 1</math>. After a few tests it's not difficult to estimate a few jumps, and it took me only a few minutes to realize the answer was somewhere in the forties (You could also use the fact that <math>45^2=2025</math>). Then it's just a matter of checking them until we get <math>\boxed{049}</math>. |
Alternatively, you could use the equation above and proceed with one of the other two solutions listed. | Alternatively, you could use the equation above and proceed with one of the other two solutions listed. | ||
-jackshi2006 | -jackshi2006 | ||
+ | |||
+ | Edited and <math>\LaTeX</math>ed by PhunsukhWangdu | ||
+ | |||
+ | ===Solution 4=== | ||
+ | |||
+ | Here is an intuitive way to approximate the answer is around <math>45</math>: For the function | ||
+ | <math>f(n)=\frac{2002}{n}</math> | ||
+ | its derivative is | ||
+ | <math>-\frac{2002}{n^2}</math>, | ||
+ | which should be close to <math>-1</math> because we need to find the smallest skipped integer. The rest of the steps are the same as Solution 1. | ||
+ | |||
+ | -maxamc | ||
== See also == | == See also == | ||
{{AIME box|year=2002|n=II|num-b=7|num-a=9}} | {{AIME box|year=2002|n=II|num-b=7|num-a=9}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 14:22, 14 July 2023
Contents
Problem
Find the least positive integer for which the equation
has no integer solutions for
. (The notation
means the greatest integer less than or equal to
.)
Solutions
Solution 1
Note that if , then either
,
or
. Either way, we won't skip any natural numbers.
The greatest such that
is
. (The inequality simplifies to
, which is easy to solve by trial, as the solution is obviously
.)
We can now compute:
From the observation above (and the fact that ) we know that all integers between
and
will be achieved for some values of
. Similarly, for
we obviously have
.
Hence the least positive integer for which the equation
has no integer solutions for
is
.
Note
After getting that , for ease of computation above, we can use the fact that
varies solely based on
and checking these gives us that the pattern fails at
giving us
as the answer.
~Dhillonr25
Solution 2
Rewriting the given information and simplifying it a bit, we have
Now note that in order for there to be no integer solutions to we must have
We seek the smallest such
A bit of experimentation yields that
is the smallest solution, as for
it is true that
Furthermore,
is the smallest such case. (If unsure, we could check if the result holds for
and as it turns out, it doesn't.) Therefore, the answer is
Solution 3
In this solution we use inductive reasoning and a lot of trial and error. Depending on how accurately you can estimate, the solution will come quicker or slower.
Using values of as
and
we can find the corresponding values of
relatively easily. For
,
is in the range
; for
,
is the the range
, etc:
. For any positive integer
is in a range of
.
Now we try testing to get a better understanding of what our solution will look like. Obviously, there will be no solution for
, but we are more interested in how the range will compute to. Using the formula we got above, the range will be
. Testing any integer
from
will result in the same range. Also, notice that each and every one of them have no solution for
. Testing
gives a range of
, and
gives
. They each have a solution for
, and their range is only one value. Therefore, we can assume with relative safety that the integer
we want is the lowest integer that follows this equation
Now we can easily guess and check starting from . After a few tests it's not difficult to estimate a few jumps, and it took me only a few minutes to realize the answer was somewhere in the forties (You could also use the fact that
). Then it's just a matter of checking them until we get
.
Alternatively, you could use the equation above and proceed with one of the other two solutions listed.
-jackshi2006
Edited and ed by PhunsukhWangdu
Solution 4
Here is an intuitive way to approximate the answer is around : For the function
its derivative is
,
which should be close to
because we need to find the smallest skipped integer. The rest of the steps are the same as Solution 1.
-maxamc
See also
2002 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 7 |
Followed by Problem 9 | |
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.