Минимальная сумма при заданном количестве: условия и конструкция

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

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

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

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

  1. Целые числа и необходимые условия
  2. Граница и достижимость
  3. Минимальная сумма при заданном количестве

    Сначала: Целые числа и необходимые условия, Граница и достижимость

  4. Проверка количества чисел

    Сначала: Минимальная сумма при заданном количестве

  5. Ответ: нет

    Сначала: Проверка количества чисел

  6. Наименьшее допустимое количество

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

  7. Ответ

    Сначала: Наименьшее допустимое количество

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

На доске написано 30 различных натуральных чисел, десятичная запись каждого из которых оканчивается или на цифру 4, или на цифру 8. Сумма написанных чисел равна 2786.

а) Может ли на доске быть поровну чисел, оканчивающихся на 4 и на 8?

б) Могут ли ровно четыре числа на доске оканчиваться на 8?

в) Какое наименьшее количество чисел, оканчивающихся на 8, может быть на доске?

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

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

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

Шаг 1. Пусть всего nn различных чисел, kk из них оканчиваются на ee, остальные на dd. Для каждой последней цифры минимальный набор - d, d+10, …d,\,d+10,\,\ldots и e, e+10, …e,\,e+10,\,\ldots . Поэтому минимальная сумма равна (n−k)d+5(n−k)(n−k−1)+ke+5k(k−1)(n-k)d+5(n-k)(n-k-1)+ke+5k(k-1). Любая другая сумма при этом kk получается прибавлением неотрицательного числа, кратного 10. Обратно, любую такую прибавку можно добавить к наибольшему числу одной из непустых групп: числа останутся различными и сохранят последние цифры.
Шаг 2. Подставляем требуемое kk. Необходимо и достаточно, чтобы заданная сумма SS была не меньше Smin⁡(k)S_{\min}(k) и разность S−Smin⁡(k)S-S_{\min}(k) делилась на 10. В таблице указаны kk, минимальная сумма и остаток разности по модулю 10.
таблица=((15;2280;6))\text{таблица}=\left(\left(15;2280;6\right)\right)
Шаг 3. Нет. Полный список допустимых вариантов пуст либо необходимое условие нарушено.
Шаг 1. Пусть всего nn различных чисел, kk из них оканчиваются на ee, остальные на dd. Для каждой последней цифры минимальный набор - d, d+10, …d,\,d+10,\,\ldots и e, e+10, …e,\,e+10,\,\ldots . Поэтому минимальная сумма равна (n−k)d+5(n−k)(n−k−1)+ke+5k(k−1)(n-k)d+5(n-k)(n-k-1)+ke+5k(k-1). Любая другая сумма при этом kk получается прибавлением неотрицательного числа, кратного 10. Обратно, любую такую прибавку можно добавить к наибольшему числу одной из непустых групп: числа останутся различными и сохранят последние цифры.
Шаг 2. Подставляем требуемое kk. Необходимо и достаточно, чтобы заданная сумма SS была не меньше Smin⁡(k)S_{\min}(k) и разность S−Smin⁡(k)S-S_{\min}(k) делилась на 10. В таблице указаны kk, минимальная сумма и остаток разности по модулю 10.
таблица=((4;3446;0))\text{таблица}=\left(\left(4;3446;0\right)\right)
Шаг 3. Нет. Полный список допустимых вариантов пуст либо необходимое условие нарушено.
Шаг 1. Пусть всего nn различных чисел, kk из них оканчиваются на ee, остальные на dd. Для каждой последней цифры минимальный набор - d, d+10, …d,\,d+10,\,\ldots и e, e+10, …e,\,e+10,\,\ldots . Поэтому минимальная сумма равна (n−k)d+5(n−k)(n−k−1)+ke+5k(k−1)(n-k)d+5(n-k)(n-k-1)+ke+5k(k-1). Любая другая сумма при этом kk получается прибавлением неотрицательного числа, кратного 10. Обратно, любую такую прибавку можно добавить к наибольшему числу одной из непустых групп: числа останутся различными и сохранят последние цифры.
Шаг 2. Проверяем целые kk от 0 до nn по доказанному необходимому и достаточному условию. В таблице перечислены все допустимые kk и их минимальные суммы. Самое маленькое kk даёт искомую нижнюю границу. Выписанный набор получен из минимального добавлением всей нужной прибавки к его наибольшему элементу и подтверждает достижимость.
таблица=((9;2616);(14;2286);(19;2456))\text{таблица}=\left(\left(9;2616\right);\left(14;2286\right);\left(19;2456\right)\right)
пример=(4;8;14;18;24;28;34;38;44;48;54;58;64;68;74;78;84;88;94;104;114;124;134;144;154;164;174;184;194;374)\text{пример}=\left(4;8;14;18;24;28;34;38;44;48;54;58;64;68;74;78;84;88;94;104;114;124;134;144;154;164;174;184;194;374\right)
Шаг 3. Записываем полученное значение.
99

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

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