Упорядоченные знаменатели

Упорядочим знаменатели. Если осталось kk дробей с суммой RR и наименьшим знаменателем xx, то 1x≤R≤kx\frac{1}{x}\leq R\leq\frac{k}{x}. Значит, ⌈1R⌉≤x≤⌊kR⌋\left\lceil \frac{1}{R}\right\rceil \leq x\leq\left\lfloor \frac{k}{R}\right\rfloor, а xx не меньше предыдущего знаменателя. Вычитаем 1x\frac{1}{x} и повторяем; при последней дроби её знаменатель однозначен. Получаем все неубывающие четвёрки с суммой 1.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Применение в задаче

Шаг 1. Упорядочим знаменатели. Если осталось kk дробей с суммой RR и наименьшим знаменателем xx, то 1x≤R≤kx\frac{1}{x}\leq R\leq\frac{k}{x}. Значит, ⌈1R⌉≤x≤⌊kR⌋\left\lceil \frac{1}{R}\right\rceil \leq x\leq\left\lfloor \frac{k}{R}\right\rfloor, а xx не меньше предыдущего знаменателя. Вычитаем 1x\frac{1}{x} и повторяем; при последней дроби её знаменатель однозначен. Получаем все неубывающие четвёрки с суммой 1.

Всё решение и условие задачи Решить задачу

Следующий шаг

Задачи по этому методу