Гарантированная сумма поднабора

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

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

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

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

  1. Сумма больше восьмидесяти
  2. Ответ: да

    Сначала: Сумма больше восьмидесяти

  3. Почему строгая граница восемьдесят два неверна

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

  4. Ответ: нет

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

  5. Сумма больше восьмидесяти

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

  6. Усиление до строгой границы восемьдесят один

    Сначала: Сумма больше восьмидесяти

  7. Ответ: да

    Сначала: Усиление до строгой границы восемьдесят один

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

Верно ли, что для любого набора положительных чисел, каждое из которых не превосходит 10, а сумма которых больше 90, всегда можно выбрать несколько чисел так, чтобы их сумма была не больше 90, но больше:

а) 80;

б) 82;

в) 81.

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

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

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

Шаг 1. Прибавляем числа, пока сумма впервые не превысит восемьдесят. Это возможно, поскольку общая сумма больше девяноста. Последнее слагаемое не больше десяти, поэтому полученная сумма не больше девяноста.
Шаг 2. Да. Приведённая конструкция удовлетворяет требуемым условиям.
Шаг 1. Берём десять одинаковых чисел 9,1. Общая сумма равна 91, каждое число не больше десяти. Все десять дают больше девяноста, а любые девять или меньше дают не больше 81,9. Значит, суммы больше 82 и не больше 90 нет.
Шаг 2. Нет. Доказанная граница или полный конечный разбор исключает возможность.
Шаг 1. Прибавляем числа, пока сумма впервые не превысит восемьдесят. Это возможно, поскольку общая сумма больше девяноста. Последнее слагаемое не больше десяти, поэтому полученная сумма не больше девяноста.
Шаг 2. Выберем поднабор с максимальной суммой A≤90A\leq 90. По предыдущему шагу A>80A>80. Предположим A≤81A\leq 81. Любое число bb вне поднабора больше g=90−A≥9g=90-A\geq 9. Элементов поднабора, не меньших bb, максимум восемь, и их сумма не больше 80. Поэтому сумма остальных, меньших bb, не меньше A−80≥b−g>0A-80\geq b-g>0. Если среди них есть элемент не меньше b−gb-g, заменяем его на bb, увеличивая AA без превышения 90. Иначе накапливаем несколько этих элементов до первой суммы δ≥b−g\delta \geq b-g. Тогда δ<2(b−g)≤2<b\delta <2(b-g)\leq 2<b; заменив их на bb, опять увеличиваем AA без превышения 90. Противоречие в обоих случаях, значит A>81A>81.
Шаг 3. Да. Приведённая конструкция удовлетворяет требуемым условиям.

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

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