Difference between revisions of "2016 AIME I Problems/Problem 14"
m (→Solution 3 (risky)) |
|||
(22 intermediate revisions by 6 users not shown) | |||
Line 7: | Line 7: | ||
First note that <math>1001 = 143 \cdot 7</math> and <math>429 = 143 \cdot 3</math> so every point of the form <math>(7k, 3k)</math> is on the line. Then consider the line <math>l</math> from <math>(7k, 3k)</math> to <math>(7(k + 1), 3(k + 1))</math>. Translate the line <math>l</math> so that <math>(7k, 3k)</math> is now the origin. There is one square and one circle that intersect the line around <math>(0,0)</math>. Then the points on <math>l</math> with an integral <math>x</math>-coordinate are, since <math>l</math> has the equation <math>y = \frac{3x}{7}</math>: | First note that <math>1001 = 143 \cdot 7</math> and <math>429 = 143 \cdot 3</math> so every point of the form <math>(7k, 3k)</math> is on the line. Then consider the line <math>l</math> from <math>(7k, 3k)</math> to <math>(7(k + 1), 3(k + 1))</math>. Translate the line <math>l</math> so that <math>(7k, 3k)</math> is now the origin. There is one square and one circle that intersect the line around <math>(0,0)</math>. Then the points on <math>l</math> with an integral <math>x</math>-coordinate are, since <math>l</math> has the equation <math>y = \frac{3x}{7}</math>: | ||
− | <cmath> (0,0), (1, \frac{3}{7}), (2, \frac{6}{7}), (3, 1 + \frac{2}{7}), (4, 1 + \frac{5}{7}), (5, 2 + \frac{1}{7}), (6, 2 + \frac{4}{7}), (7,3). </cmath> | + | <cmath> (0,0), \left(1, \frac{3}{7}\right), \left(2, \frac{6}{7}\right), \left(3, 1 + \frac{2}{7}\right), \left(4, 1 + \frac{5}{7}\right), \left(5, 2 + \frac{1}{7}\right), \left(6, 2 + \frac{4}{7}\right), (7,3). </cmath> |
− | We claim that the lower right vertex of the square centered at <math>(2,1)</math> lies on <math>l</math>. Since the square has side length <math>\frac{1}{5}</math>, the lower right vertex of this square has coordinates <math>(2 + \frac{1}{10}, 1 - \frac{1}{10}) = (\frac{21}{10}, \frac{9}{10})</math>. Because <math>\frac{9}{10} = \frac{3}{7} \cdot \frac{21}{10}</math>, <math>(\frac{21}{10}, \frac{9}{10})</math> lies on <math>l</math>. Since the circle centered at <math>(2,1)</math> is contained inside the square, this circle does not intersect <math>l</math>. Similarly the upper left vertex of the square centered at <math>(5,2)</math> is on <math>l</math>. Since every other point listed above is farther away from a lattice point (excluding (0,0) and (7,3)) and there are two squares with centers strictly between <math>(0,0)</math> and <math>(7,3)</math> that intersect <math>l</math>. Since there are <math>\frac{1001}{7} = \frac{429}{3} = 143</math> segments from <math>(7k, 3k)</math> to <math>(7(k + 1), 3(k + 1))</math>, the above count is yields <math>143 \cdot 2 = 286</math> squares. Since every lattice point on <math>l</math> is of the form <math>(3k, 7k)</math> where <math>0 \le k \le 143</math>, there are <math>144</math> lattice points on <math>l</math>. Centered at each lattice point, there is one square and one circle, hence this counts <math>288</math> squares and circles. Thus <math>m + n = 286 + 288 = \boxed{574}</math>. | + | We claim that the lower right vertex of the square centered at <math>(2,1)</math> lies on <math>l</math>. Since the square has side length <math>\frac{1}{5}</math>, the lower right vertex of this square has coordinates <math>\left(2 + \frac{1}{10}, 1 - \frac{1}{10}\right) = \left(\frac{21}{10}, \frac{9}{10}\right)</math>. Because <math>\frac{9}{10} = \frac{3}{7} \cdot \frac{21}{10}</math>, <math>\left(\frac{21}{10}, \frac{9}{10}\right)</math> lies on <math>l</math>. Since the circle centered at <math>(2,1)</math> is contained inside the square, this circle does not intersect <math>l</math>. Similarly the upper left vertex of the square centered at <math>(5,2)</math> is on <math>l</math>. Since every other point listed above is farther away from a lattice point (excluding (0,0) and (7,3)) and there are two squares with centers strictly between <math>(0,0)</math> and <math>(7,3)</math> that intersect <math>l</math>. Since there are <math>\frac{1001}{7} = \frac{429}{3} = 143</math> segments from <math>(7k, 3k)</math> to <math>(7(k + 1), 3(k + 1))</math>, the above count is yields <math>143 \cdot 2 = 286</math> squares. Since every lattice point on <math>l</math> is of the form <math>(3k, 7k)</math> where <math>0 \le k \le 143</math>, there are <math>144</math> lattice points on <math>l</math>. Centered at each lattice point, there is one square and one circle, hence this counts <math>288</math> squares and circles. Thus <math>m + n = 286 + 288 = \boxed{574}</math>. |
(Solution by gundraja) | (Solution by gundraja) | ||
+ | |||
+ | ==Solution 2== | ||
+ | |||
+ | See if you can solve the problem with the following. | ||
+ | |||
<asy>size(12cm);draw((0,0)--(7,3));draw(box((0,0),(7,3)),dotted); | <asy>size(12cm);draw((0,0)--(7,3));draw(box((0,0),(7,3)),dotted); | ||
for(int i=0;i<8;++i)for(int j=0; j<4; ++j){dot((i,j),linewidth(1));draw(box((i-.1,j-.1),(i+.1,j+.1)),linewidth(.5));draw(circle((i,j),.1),linewidth(.5));} | for(int i=0;i<8;++i)for(int j=0; j<4; ++j){dot((i,j),linewidth(1));draw(box((i-.1,j-.1),(i+.1,j+.1)),linewidth(.5));draw(circle((i,j),.1),linewidth(.5));} | ||
</asy> | </asy> | ||
− | ==Solution 2== | + | ===Solution to Solution 2=== |
This is mostly a clarification to Solution 1, but let's take the diagram for the origin to <math>(7,3)</math>. We have the origin circle and square intersected, then two squares, then the circle and square at <math>(7,3)</math>. If we take the circle and square at the origin out of the diagram, we will be able to repeat the resulting segment (with its circles and squares) end to end from <math>(0,0)</math> to <math>(1001,429)</math>, which forms the line we need without overlapping. Since <math>143</math> of these segments are needed to do this, and <math>3</math> squares and <math>1</math> circle are intersected with each, there are <math>143 \cdot (3+1) = 572</math> squares and circles intersected. Adding the circle and square that are intersected at the origin back into the picture, we get that there are <math>572+2=\boxed{574}</math> squares and circles intersected in total. | This is mostly a clarification to Solution 1, but let's take the diagram for the origin to <math>(7,3)</math>. We have the origin circle and square intersected, then two squares, then the circle and square at <math>(7,3)</math>. If we take the circle and square at the origin out of the diagram, we will be able to repeat the resulting segment (with its circles and squares) end to end from <math>(0,0)</math> to <math>(1001,429)</math>, which forms the line we need without overlapping. Since <math>143</math> of these segments are needed to do this, and <math>3</math> squares and <math>1</math> circle are intersected with each, there are <math>143 \cdot (3+1) = 572</math> squares and circles intersected. Adding the circle and square that are intersected at the origin back into the picture, we get that there are <math>572+2=\boxed{574}</math> squares and circles intersected in total. | ||
− | ==Solution | + | ===Solution to Solution 2 without a diagram=== |
− | This solution is a more systematic approach for finding when the line intersects the squares and circles. Because <math>1001 = 7*11*13</math> and <math>429=3*11*13</math>, the slope of our line is <math>\frac{3}{7}</math>, and we only need to consider the line in the rectangle from the origin to <math>(7,3)</math>, and we can iterate the line <math>11*13=143</math> times. First, we consider how to figure out if the line intersects a square. Given a lattice point <math>(x_1, y_1)</math>, we can think of representing a square centered at that lattice point as all points equal to <math>(x_1 \pm a, y_1 \pm b)</math> s.t. <math>0 \leq a,b \leq \frac{1}{10}</math>. If the line <math>y = \frac{3}{7}x</math> intersects the square, then we must have <math>\frac{y_1 + b}{x_1 + a} = \frac{3}{7}</math>. The line with the least slope that intersects the square intersects at the bottom right corner and the line with the greatest slope that intersects the square intersects at the top left corner; thus we must have that <math>\frac{3}{7}</math> lies in between these slopes, or that <math>\frac{y_1-\frac{1}{10}}{x_1+\frac{1}{10}} \leq \frac{3}{7} \leq \frac{y_1+\frac{1}{10}}{x_1-\frac{1}{10}}</math>. Simplifying, <math>3x_1 - 1 \leq 7y_1 \leq 3x_1 + 1</math>. Because <math>y</math> can only equal <math>0, 1, 2, 3</math>, we just do casework based on the values of <math>y</math> and find that the points <math>(2, 1)</math> and <math>(5, 2)</math> are intersected just at the corner of the square and <math>(0, 0), (7, 3)</math> are intersected through the center of the square. However, we disregard one of <math>(0, 0)</math> and <math>(7, 3)</math>, WLOG <math>(0, 0)</math>, since we just use it in our count for the next of the 143 segments. Therefore, in one of our "segments", 3 squares are intersected and 1 circle is intersected giving 4 total. Thus our answer is <math>143*4 = | + | This solution is a more systematic approach for finding when the line intersects the squares and circles. Because <math>1001 = 7*11*13</math> and <math>429=3*11*13</math>, the slope of our line is <math>\frac{3}{7}</math>, and we only need to consider the line in the rectangle from the origin to <math>(7,3)</math>, and we can iterate the line <math>11*13=143</math> times. First, we consider how to figure out if the line intersects a square. Given a lattice point <math>(x_1, y_1)</math>, we can think of representing a square centered at that lattice point as all points equal to <math>(x_1 \pm a, y_1 \pm b)</math> s.t. <math>0 \leq a,b \leq \frac{1}{10}</math>. If the line <math>y = \frac{3}{7}x</math> intersects the square, then we must have <math>\frac{y_1 + b}{x_1 + a} = \frac{3}{7}</math>. The line with the least slope that intersects the square intersects at the bottom right corner and the line with the greatest slope that intersects the square intersects at the top left corner; thus we must have that <math>\frac{3}{7}</math> lies in between these slopes, or that <math>\frac{y_1-\frac{1}{10}}{x_1+\frac{1}{10}} \leq \frac{3}{7} \leq \frac{y_1+\frac{1}{10}}{x_1-\frac{1}{10}}</math>. Simplifying, <math>3x_1 - 1 \leq 7y_1 \leq 3x_1 + 1</math>. Because <math>y</math> can only equal <math>0, 1, 2, 3</math>, we just do casework based on the values of <math>y</math> and find that the points <math>(2, 1)</math> and <math>(5, 2)</math> are intersected just at the corner of the square and <math>(0, 0), (7, 3)</math> are intersected through the center of the square. However, we disregard one of <math>(0, 0)</math> and <math>(7, 3)</math>, WLOG <math>(0, 0)</math>, since we just use it in our count for the next of the 143 segments. Therefore, in one of our "segments", 3 squares are intersected and 1 circle is intersected giving 4 total. Thus our answer is <math>143*4 = 572</math>. HOWEVER, we cannot forget that we ignored <math>(0, 0)</math>, which contributes another square and circle to our count, making the final answer <math>572 + 2 = \boxed{574}</math>. |
-Patrick4President | -Patrick4President | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://youtu.be/diLCwN-358s | ||
+ | |||
== See also == | == See also == | ||
{{AIME box|year=2016|n=I|num-b=13|num-a=15}} | {{AIME box|year=2016|n=I|num-b=13|num-a=15}} | ||
+ | [[Category:Intermediate Geometry Problems]] | ||
+ | [[Category:Coordinate Geometry Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 21:08, 22 November 2022
Contents
Problem
Centered at each lattice point in the coordinate plane are a circle radius and a square with sides of length
whose sides are parallel to the coordinate axes. The line segment from
to
intersects
of the squares and
of the circles. Find
.
Solution 1
First note that and
so every point of the form
is on the line. Then consider the line
from
to
. Translate the line
so that
is now the origin. There is one square and one circle that intersect the line around
. Then the points on
with an integral
-coordinate are, since
has the equation
:
We claim that the lower right vertex of the square centered at lies on
. Since the square has side length
, the lower right vertex of this square has coordinates
. Because
,
lies on
. Since the circle centered at
is contained inside the square, this circle does not intersect
. Similarly the upper left vertex of the square centered at
is on
. Since every other point listed above is farther away from a lattice point (excluding (0,0) and (7,3)) and there are two squares with centers strictly between
and
that intersect
. Since there are
segments from
to
, the above count is yields
squares. Since every lattice point on
is of the form
where
, there are
lattice points on
. Centered at each lattice point, there is one square and one circle, hence this counts
squares and circles. Thus
.
(Solution by gundraja)
Solution 2
See if you can solve the problem with the following.
Solution to Solution 2
This is mostly a clarification to Solution 1, but let's take the diagram for the origin to . We have the origin circle and square intersected, then two squares, then the circle and square at
. If we take the circle and square at the origin out of the diagram, we will be able to repeat the resulting segment (with its circles and squares) end to end from
to
, which forms the line we need without overlapping. Since
of these segments are needed to do this, and
squares and
circle are intersected with each, there are
squares and circles intersected. Adding the circle and square that are intersected at the origin back into the picture, we get that there are
squares and circles intersected in total.
Solution to Solution 2 without a diagram
This solution is a more systematic approach for finding when the line intersects the squares and circles. Because and
, the slope of our line is
, and we only need to consider the line in the rectangle from the origin to
, and we can iterate the line
times. First, we consider how to figure out if the line intersects a square. Given a lattice point
, we can think of representing a square centered at that lattice point as all points equal to
s.t.
. If the line
intersects the square, then we must have
. The line with the least slope that intersects the square intersects at the bottom right corner and the line with the greatest slope that intersects the square intersects at the top left corner; thus we must have that
lies in between these slopes, or that
. Simplifying,
. Because
can only equal
, we just do casework based on the values of
and find that the points
and
are intersected just at the corner of the square and
are intersected through the center of the square. However, we disregard one of
and
, WLOG
, since we just use it in our count for the next of the 143 segments. Therefore, in one of our "segments", 3 squares are intersected and 1 circle is intersected giving 4 total. Thus our answer is
. HOWEVER, we cannot forget that we ignored
, which contributes another square and circle to our count, making the final answer
.
-Patrick4President
Video Solution
See also
2016 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.