Maths Olympiad Prep

Library / /968 of 1394

Geometry Difficulty 5.5 AIME, harder Prove it United States

Problem:

In the Cartesian plane, let A=(0,0)A=(0,0), B=(200,100)B=(200,100), and C=(30,330)C=(30,330). Compute the number of ordered pairs (x,y)(x, y) of integers so that (x+12,y+12)\left(x+\frac{1}{2}, y+\frac{1}{2}\right) is in the interior of triangle ABCABC.

Solution

Solution:

We use Pick's Theorem, which states that in a lattice polygon with II lattice points in its interior and BB lattice points on its boundary, the area is I+B/21I + B/2 - 1. Also, call a point center if it is of the form (x+12,y+12)\left(x+\frac{1}{2}, y+\frac{1}{2}\right) for integers xx and yy.

The key observation is the following: suppose we draw in the center points, rotate 4545^{\circ} degrees about the origin and scale up by 2\sqrt{2}. Then, the area of the triangle goes to 2K2K, and the set of old lattice points and center points becomes a lattice. Hence, we can also apply Pick's theorem to this new lattice.

Let the area of the original triangle be KK, let I1I_1 and B1B_1 be the number of interior lattice points and boundary lattice points, respectively. Let IcI_c and BcB_c be the number of interior and boundary points that are center points in the original triangle. Finally, let I2I_2 and B2B_2 be the number of interior and boundary points that are either lattice points or center points in the new triangle. By Pick's Theorem on both lattices,
K=I1+B1/212K=I2+B2/21(I2I1)=KB1B22Ic=KBc2. \begin{aligned} K &= I_1 + B_1/2 - 1 \\ 2K &= I_2 + B_2/2 - 1 \\ \Longrightarrow (I_2 - I_1) &= K - \frac{B_1 - B_2}{2} \\ \Longrightarrow I_c &= K - \frac{B_c}{2}. \end{aligned}
One can compute that the area is 3150031500. The number of center points that lie on ABAB, BCBC, and CACA are 00, 1010, and 3030, respectively. Thus, the final answer is 315000+10+302=3148031500 - \frac{0 + 10 + 30}{2} = 31480.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.