Prove that an open interval of length 1/n in the real line contains at most (n+1)/2 rational points p/q with 1 ≤ q ≤ n.
Solution
This is a variant on the familiar result that m+1 integers from {1, 2, ... , 2m} must include one which divides another. To prove that, take the largest odd divisor of each of the m+1 integers. That gives us m+1 odd numbers from {1, 3, ... , 2m-1}, so by the pigeonhole principle we must have some odd integer b twice. If the corresponding integers are 2hb and 2kb, then one must divide the other.
Now if 1≤ q ≤ n and 1 ≤ kq ≤ n, then |p/q - p'/kq| ≥ 1/kq ≥ 1/n. But we cannot have two such points in an open interval of length 1/n. Obviously we cannot have two points with the same denominator, so if n = 2m, there are at most m points and if n = 2m+1 there are at most m+1 points.
© John Scholes
jscholes@kalva.demon.co.uk
24 Aug 2002