Универсальная упаковка двух групп

Последовательность применённых правил и переходов в пунктах задачи.

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

Что разобрать сначала

Переходите по порядку или откройте то правило, которое вызвало затруднение. В конкретном решении используются только нужные для его условия ветви.

  1. Почему большую сумму гарантировать нельзя
  2. Ответ: нет

    Сначала: Почему большую сумму гарантировать нельзя

  3. Почему большую сумму гарантировать нельзя

    Сначала: Ответ: нет

  4. Ответ: нет

    Сначала: Почему большую сумму гарантировать нельзя

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

    Сначала: Ответ: нет

  6. Почему большую сумму гарантировать нельзя

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

  7. Ответ

    Сначала: Почему большую сумму гарантировать нельзя

Разобранный пример

Число SS таково, что для любого представления числа SS в виде суммы положительных слагаемых, каждое из которых не превосходит 1, эти слагаемые можно разделить на две группы так, что сумма слагаемых в каждой группе не превосходит 19.

а) Может ли число SS быть равным 38?

б) Может ли число SS быть больше 37,05?

в) Найдите максимальное возможное значение SS.

Посмотреть решение

Предварительное решение, не проверено экспертом.

Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.

Шаг 1. При S>2CS>2C ограничение нарушает уже общая сумма. При C(2C+1)C+1<S≤2C\frac{C(2C+1)}{C+1}<S\leq 2C берём 2C+12C+1 равных слагаемых S2C+1\frac{S}{2C+1}, каждое не больше единицы. Одна из двух групп содержит хотя бы C+1C+1 слагаемых, и её сумма больше CC. Поэтому ни одна большая сумма не обладает универсальным свойством.
S=74120S=\frac{741}{20}
Шаг 2. Нет. Доказанная граница или полный конечный разбор исключает возможность.
Шаг 1. При S>2CS>2C ограничение нарушает уже общая сумма. При C(2C+1)C+1<S≤2C\frac{C(2C+1)}{C+1}<S\leq 2C берём 2C+12C+1 равных слагаемых S2C+1\frac{S}{2C+1}, каждое не больше единицы. Одна из двух групп содержит хотя бы C+1C+1 слагаемых, и её сумма больше CC. Поэтому ни одна большая сумма не обладает универсальным свойством.
S=74120S=\frac{741}{20}
Шаг 2. Нет. Доказанная граница или полный конечный разбор исключает возможность.
Шаг 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. Значит, обе группы помещаются.
Шаг 2. При S>2CS>2C ограничение нарушает уже общая сумма. При C(2C+1)C+1<S≤2C\frac{C(2C+1)}{C+1}<S\leq 2C берём 2C+12C+1 равных слагаемых S2C+1\frac{S}{2C+1}, каждое не больше единицы. Одна из двух групп содержит хотя бы C+1C+1 слагаемых, и её сумма больше CC. Поэтому ни одна большая сумма не обладает универсальным свойством.
Шаг 3. Записываем вычисленный результат.
74120\frac{741}{20}

Открыть задачу целиком

Попробовать самостоятельно