Почему граничная сумма всегда размещается

Пусть сумма SS не больше C(2C+1)C+1\frac{C(2C+1)}{C+1}, где CC обозначает целую вместимость каждой группы, а каждое слагаемое не больше единицы. Выберем поднабор с наибольшей суммой A≤CA\leq C. Если остальная сумма больше CC, то A<S−C≤C2C+1A<S-C\leq\frac{C^{2}}{C+1}. Каждое невыбранное слагаемое больше C−AC-A, иначе его можно добавить. Не выбранных слагаемых не меньше C+1C+1. Любые CC из них имеют сумму не больше CC и больше C(C−A)>AC(C-A)>A. Это противоречит максимальности AA. Значит, обе группы помещаются.

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

Что нужно знать

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

Шаг 1. Пусть сумма SS не больше C(2C+1)C+1\frac{C(2C+1)}{C+1}, где CC — целая вместимость каждой группы, а каждое слагаемое не больше единицы. Выберем поднабор с наибольшей суммой A≤CA\leq C. Если остальная сумма больше CC, то A<S−C≤C2C+1A<S-C\leq\frac{C^{2}}{C+1}. Каждое невыбранное слагаемое больше C−AC-A, иначе его можно добавить. Не выбранных слагаемых не меньше C+1C+1. Любые CC из них имеют сумму не больше CC и больше C(C−A)>AC(C-A)>A. Это противоречит максимальности AA. Значит, обе группы помещаются.

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

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

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