Difference between revisions of "2007 AIME II Problems/Problem 5"

Latest revision as of 23:38, 2 January 2023

Problem

The graph of the equation $9x+223y=2007$ is drawn on graph paper with each square representing one unit in each direction. How many of the $1$ by $1$ graph paper squares have interiors lying entirely below the graph and entirely in the first quadrant?

Solution

Solution 1

There are $223 \cdot 9 = 2007$ squares in total formed by the rectangle with edges on the x and y axes and with vertices on the intercepts of the equation, since the intercepts of the lines are $(223,0),\ (0,9)$ .

Count the number of squares that the diagonal of the rectangle passes through. Since the two diagonals of a rectangle are congruent, we can consider instead the diagonal $y = \frac{223}{9}x$ . This passes through 8 horizontal lines ( $y = 1 \ldots 8$ ) and 222 vertical lines ( $x = 1 \ldots 222$ ). Every time we cross a line, we enter a new square. Since 9 and 223 are relatively prime, we don’t have to worry about crossing an intersection of a horizontal and vertical line at one time. We must also account for the first square. This means that it passes through $222 + 8 + 1 = 231$ squares.

The number of non-diagonal squares is $2007 - 231 = 1776$ . Divide this in 2 to get the number of squares in one of the triangles, with the answer being $\frac{1776}2 = 888$ .

Solution 2

Count the number of each squares in each row of the triangle. The intercepts of the line are $(223,0),\ (0,9)$ .

In the top row, there clearly are no squares that can be formed. In the second row, we see that the line $y = 8$ gives a $x$ value of $\frac{2007 - 8(223)}{9} = 24 \frac 79$ , which means that $\lfloor 24 \frac 79\rfloor = 24$ unit squares can fit in that row. In general, there are

$\sum_{i=0}^{8} \lfloor \frac{223i}{9} \rfloor$

triangles. Since $\lfloor \frac{223}{9} \rfloor = 24$ , we see that there are more than $24(0 + 1 + \ldots + 8) = 24(\frac{8 \times 9}{2}) = 864$ triangles. Now, count the fractional parts. $\lfloor \frac{0}{9} \rfloor = 0, \lfloor \frac{7}{9} \rfloor = 0, \lfloor \frac{14}{9} \rfloor = 1,$ $\lfloor \frac{21}{9} \rfloor = 2, \lfloor \frac{28}{9} \rfloor = 3, \lfloor \frac{35}{9} \rfloor = 3,$ $\lfloor \frac{42}{9} \rfloor = 4, \lfloor \frac{49}{9} \rfloor = 5, \lfloor \frac{56}{9} \rfloor = 6$ . Adding them up, we get $864 + 1 + 2 + 3 + 3 + 4 + 5 + 6 = 888$ .

Solution 3

From Pick's Theorem, $\frac{2007}{2}=\frac{233}{2}-\frac{2}{2}+\frac{2I}{2}$ . In other words, $2I=1776$ and I is $888$ .

Do you see why we simply set $I$ as the answer as well? That's because every interior point, if moved down and left one (southwest direction), can have that point and the previous point create a unit square. For example, $(1, 1)$ moves to $(0, 0)$ , so the square of points ${(0, 0), (1, 0), (1, 1), (0, 1)}$ is one example. This applies, of course, for $888$ points.

Solution 4

We know that the number of squares intersected in an $m\times{n}$ rectangle is $m + n -\mbox{gcd}(m,n)$ . So if we apply that here, we get that the number of intersected squares is:

$9 + 223 - 1 = 231$ .

Now just subtract that from the total number of squares and divide by 2, since we want the number of squares below the line.

So,

$\frac{2007 - 231}{2} = \frac{1776}{2} = \fbox{888}$

@@ Line 7: / Line 7: @@
 There are <math>223 \cdot 9 = 2007</math> squares in total formed by the rectangle with edges on the x and y axes and with vertices on the intercepts of the equation, since the [[intercept]]s of the lines are <math>(223,0),\ (0,9)</math>.
-Count the number of squares that the diagonal of the rectangle passes through. Since the two diagonals of a rectangle are [[congruent]], we can consider instead the diagonal <math>y = \frac{223}{9}x</math>. This passes through 8 horizontal lines (<math>y = 1 \ldots 8</math>) and 222 vertical lines (<math>x = 1 \ldots 222</math>). At every time we cross a line, we enter a new square. Since 9 and 223 are [[relatively prime]], we don’t have to worry about crossing an intersection of a horizontal and vertical line at one time. We must also account for the first square. This means that it passes through <math>222 + 8 + 1 = 231</math> squares.
+Count the number of squares that the diagonal of the rectangle passes through. Since the two diagonals of a rectangle are [[congruent]], we can consider instead the diagonal <math>y = \frac{223}{9}x</math>. This passes through 8 horizontal lines (<math>y = 1 \ldots 8</math>) and 222 vertical lines (<math>x = 1 \ldots 222</math>). Every time we cross a line, we enter a new square. Since 9 and 223 are [[relatively prime]], we don’t have to worry about crossing an intersection of a horizontal and vertical line at one time. We must also account for the first square. This means that it passes through <math>222 + 8 + 1 = 231</math> squares.
 The number of non-diagonal squares is <math>2007 - 231 = 1776</math>. Divide this in 2 to get the number of squares in one of the triangles, with the answer being <math>\frac{1776}2 = 888</math>.
@@ Line 35: / Line 35: @@
 <math>\frac{2007 - 231}{2} = \frac{1776}{2} = \fbox{888}</math>
-=== Solution 5 (slower)===
-This is very elementary solution that doesn't require any tricks.
-First establish what the line looks like.
-We'll solve for each square by rows, since there are only 8, starting from the bottom, where <math>y=1</math>.
-When <math>y=1</math> <math>x=198.22</math>. When you picture this in your mind, it becomes clear you have to floor this number to get the largest integer value of x when <math>y=1</math>. So for the first row alone, there are 198 squares that are entirely beneath the line.
-<math>y=2</math> gives <math>x=174.44</math>, rounded to 173.
-Continue this process to <math>y=8</math>, getting numbers 198, 173, 148, 128, 99, 74, 49, and 24.
-<math>198+173+148+128+99+74+49+24=\box{888}</math>.
 == See also ==

2007 AIME II (Problems • Answer Key • Resources)
Preceded by Problem 4	Followed by Problem 6
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search