2016 AIME I Problems/Problem 14
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 .
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)
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 .
|2016 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|