2009 AIME I Problem 11

Question

Consider the set of all triangles

OPQ

where

O

is the origin and

P

and

Q

are distinct points in the plane with nonnegative integer coordinates

(x, y)

such that

41x + y = 2009.

Find the number of such distinct triangles whose area is a positive integer.

Answer

The lattice points on the line are

(i,\, 2009 - 41i)

for

i = 0,

1,

\ldots,

49

The triangle on points

i

and

j

has area

\frac{2009}{2}\,|i - j|,

an integer exactly when

i

and

j

have the same parity

The points on the line with nonnegative integer coordinates are

P_i = (i,\, 2009 - 41i)

for

i = 0,

1,

\ldots,

49

— fifty points in all. For

P = P_i

and

Q = P_j,

the shoelace formula gives

\begin{aligned} [OPQ] &= \small \frac{1}{2}\left|\,i(2009 - 41j) - j(2009 - 41i)\,\right| \\ &= \frac{2009}{2}\,|i - j|. \end{aligned}

This is automatically positive for distinct points, and since

2009

is odd, it is an integer exactly when

i - j

is even, that is, when

i

and

j

have the same parity. There are

25

even and

25

odd indices, so the number of triangles is

\binom{25}{2} + \binom{25}{2} = 300 + 300 = 600.

Problem 11 in other years