HMMT 二月 2004 · GEN2 赛 · 第 10 题

HMMT February 2004 — GEN2 Round — Problem 10

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? 2

解析

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: 3 / 4 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 2 and only if a and b are both even. Since there are 49 points with a, b both even and 2 98 total points, the probability that the path contains an even number of points is 2 2 2 2 2 98 − 49 49 (2 − 1 ) 3 = = . 2 2 2 98 49 (2 ) 4 4