Difference between revisions of "2015 AIME I Problems/Problem 14"
Expilncalc (talk | contribs) m (→"Step" Solution) |
m |
||
(9 intermediate revisions by 5 users not shown) | |||
Line 3: | Line 3: | ||
For each integer <math>n \ge 2</math>, let <math>A(n)</math> be the area of the region in the coordinate plane defined by the inequalities <math>1\le x \le n</math> and <math>0\le y \le x \left\lfloor \sqrt x \right\rfloor</math>, where <math>\left\lfloor \sqrt x \right\rfloor</math> is the greatest integer not exceeding <math>\sqrt x</math>. Find the number of values of <math>n</math> with <math>2\le n \le 1000</math> for which <math>A(n)</math> is an integer. | For each integer <math>n \ge 2</math>, let <math>A(n)</math> be the area of the region in the coordinate plane defined by the inequalities <math>1\le x \le n</math> and <math>0\le y \le x \left\lfloor \sqrt x \right\rfloor</math>, where <math>\left\lfloor \sqrt x \right\rfloor</math> is the greatest integer not exceeding <math>\sqrt x</math>. Find the number of values of <math>n</math> with <math>2\le n \le 1000</math> for which <math>A(n)</math> is an integer. | ||
− | ==Solution== | + | ==Solution 1== |
− | By considering the graph of this function, it is shown that the graph is composed of trapezoids ranging from <math>a^2</math> to <math>(a+1)^2</math> with the top made of diagonal line <math>y=ax</math>. The width of each trapezoid is <math>3, 5, 7</math>, etc. Whenever <math>a</math> is odd, the value of <math>A(n)</math> increases by an integer value, plus <math>\frac{1}{2}</math>. Whenever <math>a</math> is even, the value of <math>A(n)</math> increases by an integer value. Since each trapezoid always has an odd width, every value of <math>n</math> is not an integer when <math>a \pmod{4} \equiv 2</math>, and is an integer when <math>a \pmod{4} \equiv 0</math>. Every other value is an integer when <math>a</math> is odd. Therefore, it is simply a matter of determining the number of values of <math>n</math> where <math>a \pmod{4} \equiv 0</math> (<math>(5^2-4^2)+(9^2-8^2)+...+(29^2-28^2)</math>), and adding the number of values of <math>n</math> where <math>a</math> is odd (<math>\frac{(2^2-1^2)+(4^2-3^2)+...+(30^2-29^2)+(1000-31^2)}{2}</math>). Adding the two values gives <math>231+252=483</math>. | + | Let <math>n\ge 2</math> and define <math>a(n) = \left\lfloor \sqrt n \right\rfloor</math>. For <math>2\le n \le 1000</math>, we have <math>1\le a(n)\le 31</math>. |
+ | |||
+ | For <math>a^2 \le x < (a+1)^2</math> we have <math>y=ax</math>. Thus <math>A(n+1)-A(n)=a(n+\tfrac 12) = \Delta_n</math> (say), and <math>\Delta_n</math> is an integer if <math>a</math> is even; otherwise <math>\Delta_n</math> is an integer plus <math>\tfrac 12</math>. | ||
+ | |||
+ | If <math>a=1</math>, <math>n\in \{1,2,3\}</math> and <math>\Delta_n</math> is of the form <math>k(n)+\tfrac 12</math> so <math>A(n)</math> is an integer when <math>n</math> is even. | ||
+ | |||
+ | If <math>a=2</math>, <math>n\in\{4,\ldots , 8\}</math> and <math>\Delta_n</math> is an integer for all <math>n</math>. Since <math>A(3)</math> is not an integer, so <math>A(n)</math> is not an integer for any <math>n</math>. | ||
+ | |||
+ | If <math>a=3</math>, <math>n\in\{9,\ldots , 15\}</math> and <math>\Delta_n</math> is of the form <math>k(n)+\tfrac 12</math>. Since <math>A(8)</math> is of the form <math>k+\tfrac 12</math> so <math>A(n)</math> is an integer only when <math>n</math> is odd. | ||
+ | |||
+ | If <math>a=4</math>, <math>n\in\{16,\ldots , 24\}</math> and <math>\Delta_n</math> is an integer for all <math>n</math>. Since <math>A(15)</math> is an integer so <math>A(n)</math> is an integer for all <math>n</math>. | ||
+ | |||
+ | Now we are back to where we started; i.e., the case <math>a=5</math> will be the same as <math>a=1</math> and so on. Thus, | ||
+ | <cmath> | ||
+ | \begin{align} | ||
+ | a(n)\equiv 1\pmod 4 \qquad &\Longrightarrow \qquad A(n) \in \mathbb{Z} \textrm{ for even } n, \\ | ||
+ | a(n)\equiv 2\pmod 4 \qquad &\Longrightarrow \qquad A(n) \not\in \mathbb{Z} \textrm{ for any } n, \\ | ||
+ | a(n)\equiv 3\pmod 4 \qquad &\Longrightarrow \qquad A(n) \in \mathbb{Z} \textrm{ for odd } n, \\ | ||
+ | a(n)\equiv 0\pmod 4 \qquad &\Longrightarrow \qquad A(n) \in \mathbb{Z} \textrm{ for all } n. | ||
+ | \end{align} | ||
+ | </cmath> | ||
+ | |||
+ | For each <math>a</math> there are <math>2a+1</math> corresponding values of <math>n</math>: i.e., <math>n\in \{a^2, \ldots , (a+1)^2-1\}</math>. | ||
+ | |||
+ | Thus, the number of values of <math>n</math> corresponding to <math>(4)</math> (i.e., <math>a(n)\equiv 0\pmod 4</math>) is given by <cmath>\sum_{\substack{a=4k \\ a\le 31}}(2a+1) = \sum_{k=1}^7 (8k+1)=231.</cmath> | ||
+ | |||
+ | The cases <math>(1)</math> and <math>(3)</math> combine to account for half the values of <math>n</math> corresponding to odd values of <math>a(n)</math>; i.e., | ||
+ | <cmath>\frac 12 \cdot \sum_{\substack{a=2k+1 \\ a\le 31}} (2a+1) = \sum_{k=0}^{15} (2k+\tfrac 32) = 264</cmath>However, this also includes the odd integers in <math>\{1001, \ldots , 1023\}</math>. Subtracting <math>12</math> to account for these, we get the number of values of <math>n</math> corresponding to cases <math>(1)</math> and <math>(3)</math> to be <math>264-12=252</math>. | ||
+ | |||
+ | Adding the contributions from all cases we get our answer to be <math>231+252= \boxed{483}</math>. | ||
+ | |||
+ | ==Solution 2== | ||
+ | |||
+ | By considering the graph of this function, it is shown that the graph is composed of trapezoids ranging from <math>a^2</math> to <math>(a+1)^2</math> with the top made of diagonal line <math>y=ax</math>. The width of each trapezoid is <math>3, 5, 7</math>, etc. Whenever <math>a</math> is odd, the value of <math>A(n)</math> increases by an integer value, plus <math>\frac{1}{2}</math>. Whenever <math>a</math> is even, the value of <math>A(n)</math> increases by an integer value. Since each trapezoid always has an odd width, every value of <math>n</math> is not an integer when <math>a \pmod{4} \equiv 2</math>, and is an integer when <math>a \pmod{4} \equiv 0</math>. Every other value is an integer when <math>a</math> is odd. Therefore, it is simply a matter of determining the number of values of <math>n</math> where <math>a \pmod{4} \equiv 0</math> (<math>(5^2-4^2)+(9^2-8^2)+...+(29^2-28^2)</math>), and adding the number of values of <math>n</math> where <math>a</math> is odd (<math>\frac{(2^2-1^2)+(4^2-3^2)+...+(30^2-29^2)+(1000-31^2)}{2}</math>). Adding the two values gives <math>231+252=\boxed{483}</math>. | ||
=="Step" Solution== | =="Step" Solution== | ||
− | First, draw a graph of the function. Note that it is just a bunch of line segments. Since we only need to know whether or not <math>A(n)</math> is an integer, we can take the area of each piece from some <math>x</math> to <math>x+1</math> (mod 1), aka the piece from <math>2</math> to <math>3</math> has area <math>\frac{1}{2} (\mod 1)</math>. There are some patterns. Every time we increase <math>n</math> starting with <math>2</math>, we either add <math>0 (\mod 1)</math> or <math>\frac{1}{2} (\mod 1)</math>. We look at <math>\ | + | First, draw a graph of the function. Note that it is just a bunch of line segments. Since we only need to know whether or not <math>A(n)</math> is an integer, we can take the area of each piece from some <math>x</math> to <math>x+1</math> (mod 1), aka the piece from <math>2</math> to <math>3</math> has area <math>\frac{1}{2} (\mod 1)</math>. There are some patterns. Every time we increase <math>n</math> starting with <math>2</math>, we either add <math>0 (\mod 1)</math> or <math>\frac{1}{2} (\mod 1)</math>. We look at <math>\lfloor \sqrt{x} \rfloor</math> for inspiration. Every time this floor (which is really the slope) is odd, there is always an addition of <math>\frac{1}{2} (\mod 1)</math>, and whenever that slope is even, that addition is zero. |
− | Take a few cases. For slope <math>=1</math>, we see that only one value satisfies. Because the last value, <math>n=4</math>, fails, and the numbers <math>n</math> which have a slope of an even number don't change this modulus, all these do not satisfy the criterion. The pattern then comes back to the odds, and this time <math>\ | + | Take a few cases. For slope <math>=1</math>, we see that only one value satisfies. Because the last value, <math>n=4</math>, fails, and the numbers <math>n</math> which have a slope of an even number don't change this modulus, all these do not satisfy the criterion. The pattern then comes back to the odds, and this time <math>\lfloor \frac{7}{2} \rfloor + 1 = 4</math> values work. Since the work/fail pattern alternates, all the <math>n</math>s with even slope, <math>[17, 25]</math>, satisfy the criterion. This pattern is cyclic over period 4 of slopes. |
Even summation of working cases: <math>9+17+25+...+57 = 231</math>. | Even summation of working cases: <math>9+17+25+...+57 = 231</math>. | ||
Odd summation: <math>1+4+5+8+9+12...+29</math> and plus the <math>20</math> cases from <math>n=[962, 1000]</math>: <math>252</math>. Answer is <math>\boxed{483}</math>. | Odd summation: <math>1+4+5+8+9+12...+29</math> and plus the <math>20</math> cases from <math>n=[962, 1000]</math>: <math>252</math>. Answer is <math>\boxed{483}</math>. | ||
+ | |||
+ | |||
+ | |||
+ | ==Video Solution== | ||
+ | https://youtu.be/tup11-90Bqw | ||
+ | |||
+ | ~MathProblemSolvingSkills.com | ||
+ | |||
+ | |||
+ | |||
==See Also== | ==See Also== | ||
{{AIME box|year=2015|n=I|num-b=13|num-a=15}} | {{AIME box|year=2015|n=I|num-b=13|num-a=15}} | ||
+ | |||
+ | [[Category:Intermediate Geometry Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 18:58, 5 August 2023
Problem
For each integer , let
be the area of the region in the coordinate plane defined by the inequalities
and
, where
is the greatest integer not exceeding
. Find the number of values of
with
for which
is an integer.
Solution 1
Let and define
. For
, we have
.
For we have
. Thus
(say), and
is an integer if
is even; otherwise
is an integer plus
.
If ,
and
is of the form
so
is an integer when
is even.
If ,
and
is an integer for all
. Since
is not an integer, so
is not an integer for any
.
If ,
and
is of the form
. Since
is of the form
so
is an integer only when
is odd.
If ,
and
is an integer for all
. Since
is an integer so
is an integer for all
.
Now we are back to where we started; i.e., the case will be the same as
and so on. Thus,
For each there are
corresponding values of
: i.e.,
.
Thus, the number of values of corresponding to
(i.e.,
) is given by
The cases and
combine to account for half the values of
corresponding to odd values of
; i.e.,
However, this also includes the odd integers in
. Subtracting
to account for these, we get the number of values of
corresponding to cases
and
to be
.
Adding the contributions from all cases we get our answer to be .
Solution 2
By considering the graph of this function, it is shown that the graph is composed of trapezoids ranging from to
with the top made of diagonal line
. The width of each trapezoid is
, etc. Whenever
is odd, the value of
increases by an integer value, plus
. Whenever
is even, the value of
increases by an integer value. Since each trapezoid always has an odd width, every value of
is not an integer when
, and is an integer when
. Every other value is an integer when
is odd. Therefore, it is simply a matter of determining the number of values of
where
(
), and adding the number of values of
where
is odd (
). Adding the two values gives
.
"Step" Solution
First, draw a graph of the function. Note that it is just a bunch of line segments. Since we only need to know whether or not is an integer, we can take the area of each piece from some
to
(mod 1), aka the piece from
to
has area
. There are some patterns. Every time we increase
starting with
, we either add
or
. We look at
for inspiration. Every time this floor (which is really the slope) is odd, there is always an addition of
, and whenever that slope is even, that addition is zero.
Take a few cases. For slope , we see that only one value satisfies. Because the last value,
, fails, and the numbers
which have a slope of an even number don't change this modulus, all these do not satisfy the criterion. The pattern then comes back to the odds, and this time
values work. Since the work/fail pattern alternates, all the
s with even slope,
, satisfy the criterion. This pattern is cyclic over period 4 of slopes.
Even summation of working cases: .
Odd summation:
and plus the
cases from
:
. Answer is
.
Video Solution
~MathProblemSolvingSkills.com
See Also
2015 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 13 |
Followed by Problem 15 | |
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.