AIME II Problem 5 2007

[zefuri]

The graph of the equation [unparseable or potentially dangerous latex formula] is drawn on graph paper with each square representing one unit in each direction. How many of the [unparseable or potentially dangerous latex formula] graph paper squares have interiors lying entirely below the graph and entirely in the first quadrant?

[AuSmith]

The first solution here is more natural, but I think it's a little easier to go wrong in the counting argument than the second solution.

First solution: Look at the rectangle with corners at [unparseable or potentially dangerous latex formula] and [unparseable or potentially dangerous latex formula]. This rectangle has [unparseable or potentially dangerous latex formula] squares. We want to subtract out the squares that the line penetrates, then divide the remaining number of squares by 2. How many squares does the line penetrate? Well, traversing the line from [unparseable or potentially dangerous latex formula] to [unparseable or potentially dangerous latex formula], we enter a new square each time we hit a gridline. We expect to cross [unparseable or potentially dangerous latex formula] and [unparseable or potentially dangerous latex formula], except the crossings at [unparseable or potentially dangerous latex formula] and [unparseable or potentially dangerous latex formula] represent the same square.

Therefore, there are [unparseable or potentially dangerous latex formula] squares in the rectangle with corners at [unparseable or potentially dangerous latex formula] and [unparseable or potentially dangerous latex formula] that do not intersect the line. We only want one side. [unparseable or potentially dangerous latex formula]

Second solution: From here on, I will call points [unparseable or potentially dangerous latex formula] in the plane just "points" when [unparseable or potentially dangerous latex formula] are integers. These are sometimes called "lattice points."

Notice that this is dealing with the area of a polygon on a grid, and that the number of squares completely covered by the triangle is the same as the number of points in the interior of the triangle (the region bounded by the given line in the first quadrant). All these things in bold are parts of Pick's Theorem, which states that the area of a polygon on a grid (with points as vertices) is [unparseable or potentially dangerous latex formula] where I is the number of points in the interior and E is the number of points on the periphery.

Again, you can see that the number of squares covered by the mongo triangle is the same as [unparseable or potentially dangerous latex formula], the number of points in the interior, by relating each point to the square on its bottom left. Now, we can easily find the area of the triangle, and Pick gives us a formula for the area that depends on [unparseable or potentially dangerous latex formula].

[unparseable or potentially dangerous latex formula]

Find E: E is the number of points sitting on the edges of that triangle. The two legs on the x- and y- axes have [unparseable or potentially dangerous latex formula] points. The points on the hypotenuse will be integer solutions to the equation [unparseable or potentially dangerous latex formula] and so will be solutions to the equations

[unparseable or potentially dangerous latex formula]

and

[unparseable or potentially dangerous latex formula].

Therefore, the only points on the hypotenuse are [unparseable or potentially dangerous latex formula] and [unparseable or potentially dangerous latex formula], which were included when we counted the number of points on the legs. Finally, [unparseable or potentially dangerous latex formula]. From Pick's Theorem,

[unparseable or potentially dangerous latex formula]

[unparseable or potentially dangerous latex formula]

[unparseable or potentially dangerous latex formula]

[unparseable or potentially dangerous latex formula]

and, [unparseable or potentially dangerous latex formula]