What is the smallest integer n > 0 such that for any integer m in the range 1, 2, 3, ... , 1992 we can always find an integral multiple of 1/n in the open interval (m/1993, (m + 1)/1994)?
Solution
Answer: 1993 + 1994 = 3987.
Easy.
For positive a, b, a', b', with a/b < a'/b', we have that a/b < (a+a')/(b+b') < a'/b'. So certainly m/1993 < (2m+1)/3987 < (m+1)/1994. The question is whether a smaller number also works.
The simplest idea is to try the extreme value m = 1992. That gives: 1992/1993 < k/n < 1993/1994. Subtracting from 1 gives: 1/1993 > k'/n > 1/1994, where k' = n - k, or 1993k' < n < 1994k'. That is clearly not possible for k' = 1, so the smallest possible n corresponds to k' = 2 and is 3987.
© John Scholes
jscholes@kalva.demon.co.uk
12 Dec 1998