Математика · объяснение и практика
Как разложить положительную дробь на сумму единичных
Разложите положительную правильную дробь на различные единичные с помощью жадного шага и докажите, почему остаток заканчивается.

В теме Теория чисел: углубление · Учебная карта
Главная мысль
Для несократимой дроби 0<a/b<1 выбирают n=⌈b/a⌉ и вычитают 1/n. Остаток неотрицателен, а его положительный числитель после сокращения меньше прежнего, поэтому процесс конечен.
Единица в каждом числителе
Единичная дробь имеет вид 1/n при положительном целом знаменателе. В рассматриваемом разложении требуем разные знаменатели и положительные слагаемые. Повторять одну и ту же дробь сколько угодно нельзя: запись a/b как суммы a копий 1/b не решает эту более содержательную задачу. Дальше работаем с правильной положительной дробью в сокращённой форме.
Жадный шаг выбирает самую большую единичную дробь, не превосходящую остаток. Условие 1/n≤a/b равносильно n≥b/a, поэтому минимальный допустимый знаменатель равен округлению b/a вверх. Если отношение целое, остаток уже единичный и процесс заканчивается одним слагаемым. Во всех остальных случаях после вычитания остаётся меньшая положительная дробь.
Выполните шаги без округления десятичных
Для 5/11 выбираем знаменатель три. После вычитания 1/3 остаётся 4/33. Следующий знаменатель девять, остаток после 1/9 равен 1/99. Получили 5/11=1/3+1/9+1/99. Проверить сумму можно в точных обычных дробях; десятичные приближения в выборе потолка создают ненужный риск пограничной ошибки.
Почему знаменатели различаются? Ненулевой остаток после выбора n меньше 1/n. Действительно, до шага a/b<1/(n−1), а вычитание 1/n оставляет меньше 1/(n(n−1)), что не больше 1/n при n≥2. Поэтому на следующем шаге такая же или более крупная единичная дробь уже не подходит. Здесь существенно исходное условие правильности дроби.
Пример
Разложите 3/7 жадным способом.
Берём 1/3 и получаем остаток 2/21. Затем берём 1/11: остаток равен 1/231. Проверка по общему знаменателю 231 даёт 77+21+1=99, то есть 99/231=3/7.
Что убывает, если знаменатели растут
После вычитания остаток имеет вид (an−b)/(bn). Из определения потолка следует 0≤an−b<a. Если остаток ненулевой, его числитель после сокращения тоже меньше старого положительного числителя. Именно эта целочисленная мера доказывает завершение. Большие знаменатели не опровергают доказательство: уменьшается другая характеристика.
Жадный алгоритм находит некоторое разложение, но не обещает минимальное число слагаемых или небольшие знаменатели. У одной дроби могут быть разные корректные представления. Например, разбиение 1/n на 1/(n+1)+1/(n(n+1)) создаёт новые возможности, хотя нужно следить за неповторением уже имеющихся знаменателей. Требование оптимальности потребовало бы отдельной задачи и доказательства.
От чтения к действию
А теперь — вы
Частые вопросы
Жадное разложение всегда самое короткое?
Нет. Метод гарантирует конечное корректное представление правильной рациональной дроби, но не оптимальное число слагаемых.
Как проверить готовое разложение?
Сложить все единичные дроби в точной арифметике и проверить равенство исходному числу, положительность и различие знаменателей.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Округление к меньшему и большему целому: отрицательные числа
Различаем два направленных округления целого результата, особенно слева от нуля, и выбираем операцию по смыслу ограничения.
Открыть темуБесконечный спуск: почему меньших положительных решений не хватит
Разберите доказательство невозможности целочисленного решения: выберите положительную меру, сохраните уравнение и постройте строго меньшее решение.
Открыть тему