«Последовательности Фарея» (Farey sequence, или ряды Фарея, дроби Фарея, таблица Фарея) — семейство конечных подмножеств рациональных чисел с особыми, математически красивыми, свойствами.
Последовательность Фарея n-го порядка — возрастающая последовательность F_n всех неотрицательных несократимых дробей, не превосходящих 1, знаменатели которых меньше или равны n. Дроби \frac{0}{1} и \frac{1}{1} считаются первым и последним элементами F_n.
Дроби располагаются в порядке возрастания:
Определение множества F_n и последовательности Фарея до n=5
Джон Фарей (1766–1826, John Farey) — английский геолог, писатель. Один из пионеров геофизики. Автор многочисленных научных работ в области геологии, метрологии, садоводства, музыки. Его единственным вкладом в математику были дроби, названные его именем. Это результат его исследований математики звука.
В 1816 году была опубликована краткая статья Фарея «Об интересном свойстве обыкновенных дробей», в которой он определил последовательность F_n.
Эта статья дошла до французского математика О. Л. Коши, который в том же году опубликовал доказательство гипотезы Фарея о том, что каждый новый член последовательности Фарея порядка n является медиантой своих соседей.
Понятие медианты двух дробей введено А. Я. Хинчиным в теории цепных дробей. Медианта двух обыкновенных дробей \frac{a}{b} и \frac{c}{d} равна отношению суммы их числителей к сумме знаменателей: \frac{a+c}{b+d}.
Последовательность Фарея порядка n+1 можно построить рекурсивно из последовательности порядка n по следующему правилу:
- Копируем все элементы последовательности порядка n.
- Если сумма знаменателей в двух соседних дробях последовательности порядка n даёт число не большее, чем n+1, то вставляем между этими дробями их медианту.
Давайте проделаем небольшой эксперимент и получим опыт работы с последовательностями Фарея. Вот пробные задания для этого:
- Попытайтесь самостоятельно построить последовательность F_6.
- Докажите, что если \frac{a}{b}<\frac{c}{d} — две соседние дроби в последовательности Фарея F_n, то bc-ad=1. Справедливо и обратное утверждение: если дроби \frac{a}{b}<\frac{c}{d} таковы, что bc-ad=1, то они представляют собой соседние члены ряда Фарея F_n, где n=\max(b,d).
- Медианта двух дробей обладает таким замечательным свойством: она лежит между ними. Попробуйте это доказать.
Если \frac{a}{b}<\frac{c}{d}, то \frac{a}{b}<\frac{a+c}{b+d}<\frac{c}{d}. - Всех несократимых дробей со знаменателями, равными n, имеется в точности \varphi(n) (это известная в теории чисел функция Эйлера). Обозначив через L_n длину последовательности F_n, получим рекуррентное соотношение:
L_n=L_{n-1}+\varphi(n).
У последовательностей Фарея очень много интересных приложений, в том числе в олимпиадной математике. Существуют различные алгоритмы генерации всех дробей F_n, которые исследуются в информатике. Также последовательности Фарея дают интересные темы и для научно-исследовательских работ.
__________
Ответы
- Ответ:
- Доказательство прямой теоремы индукцией по n.
n=1, F_1 состоит из пары \frac{0}{1} и \frac{1}{1}.
Оценим шаг индукции при переходе из n в n+1.
Пусть \frac{a}{b}<\frac{c}{d} и bc-ad=1. При переходе в следующую последовательность Фарея между ними вставляется медианта \frac{a+c}{b+d}. Докажем, что искомое соотношение выполняется и для новых пар.
• Пара \frac{a}{b} и \frac{a+c}{b+d}:
• Пара \frac{a+c}{b+d} и \frac{c}{d}: