Задача
Рассмотрим все рациональные числа между нулём и единицей, знаменатели которых не превосходят n, расположенные в порядке возрастания (ряд Фарея). Пусть a/b и c/d – какие-то два соседних числа (дроби несократимы). Доказать, что |bc – ad| = 1.
Решение
Решение 1: Можно считать, что a/b < c/d. Неравенство a/b < a/b–1 ≤ a+1/b, которое выполняется при a + 1 ≤ b, показывает, что b ≠ d, то есть знаменатели двух соседних дробей не могут быть одинаковыми.
Докажем требуемое утверждение индукцией по n.
База. При n = 3 получаем числа ⅓, ½, ⅔; для них утверждение легко проверяется.
Шаг индукции. При переходе от n − 1 к n к старому набору чисел добавляются некоторые числа вида k/n. Согласно сделанному выше замечанию два новых числа не могут быть соседними, поэтому a/b < k/n < c/d, где a/b и c/d – соседние числа из старого списка. Нужно доказать, что оба числа
A = kb − an и B = cn − kd равны 1 (ясно, что эти числа положительны).
Предположим, что одно из них больше 1. Тогда b + d < bB + dA = (bc − ad)n = n (bc − ad = 1 по предположению индукции). Неравенство
a/b < a+c/b+d < c/d показывает, что числа a/b и c/d не могут быть соседними. Противоречие.
Решение 2: Сопоставим каждой несократимой дроби a/b точку с координатами (a, b). Если a/b и c/d – соседние члены ряда Фарея, то треугольник с вершинами
(0, 0), (a, b) и (c, d) не содержит целочисленных точек, отличных от вершин. Действительно, если бы целочисленная точка (p, q) принадлежала этому треугольнику, то числа p и q не превосходили бы n и дробь p/q была бы заключена между a/b и c/d. Поэтому согласно формуле Пика площадь этого треугольника равна ½. С другой стороны, согласно задаче 157659 его площадь равна ½ |ad – bc|.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь