Математика · объяснение и практика

Как разложить положительную дробь на сумму единичных

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

Синяя и оранжевая половины складываются в целый круг.

В теме Теория чисел: углубление · Учебная карта

Главная мысль

Для несократимой дроби 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)) создаёт новые возможности, хотя нужно следить за неповторением уже имеющихся знаменателей. Требование оптимальности потребовало бы отдельной задачи и доказательства.

От чтения к действию

А теперь — вы

Какую единичную дробь первым выберет жадный алгоритм для 4/13?

Частые вопросы

Жадное разложение всегда самое короткое?

Нет. Метод гарантирует конечное корректное представление правильной рациональной дроби, но не оптимальное число слагаемых.

Как проверить готовое разложение?

Сложить все единичные дроби в точной арифметике и проверить равенство исходному числу, положительность и различие знаменателей.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться