Let’s consider the values that the expression f(i, j) = i / n - j / m takes, where i, j \in Z for fixed n and m. For example, f(n, m) = n / n - m / m = 0.
Let’s consider, for instance, the function f(i, j) = i / 3 - j / 5. Then
f(i, j) = {5i - 3j \over 15}
According to the extended Euclidean algorithm, there always exist integers i and j, such that i / 3 - j / 5 = 1. Therefore, the smallest positive value that the expression i / 3 - j / 5 can take is 1/15. From this, it follows that this expression can take all possible values of the form k/15, where k \in Z.
Theorem. If f(i, j) = i / n - j / m, then this function takes values of the form k / LCM(n, m), where k \in Z.
Proof. Indeed,
f(i, j) = i / n - j / m = {i \cdot m - j \cdot n \over n \cdot m} = \\
{(i \cdot m) / GCD(n, m) - (j \cdot n) / GCD(n, m) \over (n \cdot m) / GCD(n, m)} = {i \cdot (m / GCD(n, m)) - j \cdot (n / GCD(n, m)) \over LCM(n, m)}
Since the numbers m / GCD (n, m) and n / GCD(n, m) are coprime, there always exists integers i and j such that the numerator of the fraction equals 1. Therefore, the function f(i, j) can take all possible values of the form k / LCM(n, m), where k ∈ Z.
Now let's consider the original function
f(t) = min_{i,j \in Z} |{i \over n} - {j \over m} + t|
Its values are the distances from the point t to the nearest point of the form k / LCM(n, m), where k \in Z. To maximize the function f(t), the value of t should be chosen so that it is exactly in the middle between the neighboring points k / LCM(n, m) and (k + 1) / LCM(n, m), where k is an integer. The value of the function at such a point is 1 / 2 \cdot LCM(n, m), which will be the answer.
Example
Let f(t) = min_{i,j \in Z} |{i \over 3} - {j \over 5} + t|. It is obvious that f(0) = 0. The equality f(1 / 15) = 0 holds because there exist integers i and j such that i / 3 - j / 5 = -1 / 15 (for example, i = 1, j = 2). From this, it also follows that f(k / 15) = 0, where k \in Z.
However, f(k / 15 + 1 / 30) = 1 / 30, and this will be the maximum value of the function, as the point k / 15 + 1 / 30 is at the maximum distance from the zeros of the function.
Comments