Library / Harvard-MIT Mathematics Tournament /291 of 352

Harvard-MIT Mathematics Tournament

Number theory Difficulty 5.5 AIME, harder Prove it United States

Problem:
A lattice point is a point whose coordinates are both integers. Suppose Johann walks in a line from the point $(0,2004)$ to a random lattice point in the interior (not on the boundary) of the square with vertices $(0,0)$ , $(0,99)$ , $(99,99)$ , $(99,0)$ . What is the probability that his path, including the endpoints, contains an even number of lattice points?

Solution

Solution:
If Johann picks the point $(a, b)$ , the path will contain $\gcd(a, 2004-b)+1$ points. There will be an odd number of points in the path if $\gcd(a, 2004-b)$ is even, which is true if and only if $a$ and $b$ are both even. Since there are $49^{2}$ points with $a, b$ both even and $98^{2}$ total points, the probability that the path contains an even number of points is

$\frac{98^{2}-49^{2}}{98^{2}}=\frac{49^{2}\left(2^{2}-1^{2}\right)}{49^{2}\left(2^{2}\right)}=\frac{3}{4} .$

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

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