Розглянемо, які значення приймає вираз f(i, j) = i / n - j / m, де i, j \in Z при фіксованих n і m. Наприклад, f(n, m) = n / n - m / m = 0.
Розглянемо, наприклад, функцію f(i, j) = i / 3 - j / 5. Тоді
f(i, j) = {5i - 3j \over 15}
Згідно з розширеним алгоритмом Евкліда, завжди існують такі цілі i і j, що i / 3 - j / 5 = 1. Отже, найменшим додатним значенням, яке може приймати вираз i / 3 - j / 5, є 1/15. Звідси випливає, що цей вираз може приймати всі можливі значення виду k/15, де k \in Z.
Теорема. Якщо f(i, j) = i / n - j / m, то ця функція приймає значення виду k / НСК(n, m), де k \in Z.
Доказ. Дійсно,
f(i, j) = i / n - j / m = {i \cdot m - j \cdot n \over n \cdot m} = \\
{(i \cdot m) / НОД(n, m) - (j \cdot n) / НОД(n, m) \over (n \cdot m) / НОД(n, m)} = {i \cdot (m / НОД(n, m)) - j \cdot (n / НОД(n, m)) \over НСК(n, m)}
Оскільки числа m / НОД(n, m) і n / НОД(n, m) є взаємно простими, то завжди існують такі i і j, що чисельник дробу дорівнює 1. Отже, функція f(i, j) може приймати всі можливі значення виду k / НСК(n, m), де k \in Z.
Тепер розглянемо початкову функцію
f(t) = min_{i,j \in Z} |{i \over n} - {j \over m} + t|
Її значення — відстані від точки t до найближчої точки виду k / НСК(n, m), k \in Z. Для максимізації функції f(t) значення t слід вибрати таким чином, щоб воно знаходилося точно посередині між сусідніми точками k / НСК(n, m) і (k + 1) / НСК(n, m), де k — ціле число. Значення функції в такій точці дорівнює 1 / 2 \cdot НСК(n, m), що й буде відповіддю.
Приклад
Нехай f(t) = min_{i,j \in Z} |{i \over 3} - {j \over 5} + t|. Очевидно, що f(0) = 0. Рівність f(1 / 15) = 0 справедлива, оскільки існують такі i і j, що i / 3 - j / 5 = -1 / 15 (наприклад, i = 1, j = 2). З цього також випливає, що f(k / 15) = 0, де k \in Z.
Проте f(k / 15 + 1 / 30) = 1 / 30, і це буде найбільшим значенням функції, оскільки точка k / 15 + 1 / 30 знаходиться на максимальній відстані від нулів функції.
Коментарі