|
|
 |
Условие
Рассмотрим все рациональные числа между нулём и единицей, знаменатели которых не превосходят 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. Поэтому согласно формуле Пика площадь этого треугольника равна ½. С другой стороны, согласно задаче 57659 его площадь равна ½ |ad – bc|.
Замечания
Обсуждение разных вопросов, связанных с рядом Фарея, см. в статье В.Н. Вагутена "Близкие дроби".
Источники и прецеденты использования
| олимпиада | |
| Название | Московская математическая олимпиада |
| год | |
| Номер | 35 |
| Год | 1972 |
| вариант | |
| Класс | 10 |
| Тур | 2 |
| задача | |
| Номер | 4 |
| книга | |
| Автор | Прасолов В.В. |
| Год издания | 2001 |
| Название | Задачи по планиметрии |
| Издательство | МЦНМО |
| Издание | 4* |
| глава | |
| Номер | 24 |
| Название | Целочисленные решетки |
| Тема | Целочисленные решетки |
| параграф | |
| Номер | 2 |
| Название | Формула Пика |
| Тема | Теорема Пика |
| задача | |
| Номер | 24.005б |
| журнал | |
| Название | "Квант" |
| год | |
| Год | 1974 |
| выпуск | |
| Номер | 12 |
| Задача | |
| Номер | М298 |
