Количество блоков единиц: условия и конструкция

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

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

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

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

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

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

  4. Проверка заданной суммы

    Сначала: Количество блоков единиц

  5. Ответ: да

    Сначала: Проверка заданной суммы

  6. Ответ: нет

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

  7. Максимум четырёхзначной суммы

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

  8. Ответ

    Сначала: Максимум четырёхзначной суммы

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

На доске написано nn единиц подряд. Между некоторыми из них расставляют знаки « ++ » и считают получившуюся сумму. Например, если было написано 10 единиц, то можно получить сумму 136: 1+1+111+11+11+1=1361+1+111+11+11+1=136.

а) Можно ли получить сумму 113, если n=50?n=50?

б) Можно ли получить сумму 114, если n=50?n=50?

в) Какую наибольшую четырёхзначную сумму можно получить, если n=50?n=50?

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

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

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

Шаг 1. Если сумма не превосходит 9999, блок из пяти единиц невозможен: 11111 уже больше суммы, а все слагаемые положительны. Поэтому достаточно блоков 1, 11, 111 и 1111. Их количества обозначим x1x_{1}, x2x_{2}, x3x_{3}, x4x_{4}. Тогда число исходных единиц n=x1+2x2+3x3+4x4n=x_{1}+2x_{2}+3x_{3}+4x_{4}, а сумма T=x1+11x2+111x3+1111x4T=x_{1}+11x_{2}+111x_{3}+1111x_{4}. Вычитая, получаем T−n=9x2+108x3+1107x4T-n=9x_{2}+108x_{3}+1107x_{4}.
T=x1+11x2+111x3+1111x4T=x_1+11 x_2+111 x_3+1111 x_4
n=x1+2x2+3x3+4x4n=x_1+2 x_2+3 x_3+4 x_4
Шаг 2. Необходимо, чтобы T−nT-n делилось на 9. Для каждого целого x4x_{4} от 0 до min⁡(n4, T1111)\min\left(\frac{n}{4},\,\frac{T}{1111}\right) и x3x_{3} от 0 до min⁡(n−4x43, T−1111x4111)\min\left(\frac{n-4x_{4}}{3},\,\frac{T-1111x_{4}}{111}\right) из равенства для T−nT-n однозначно находим x2x_{2}, затем x1x_{1}. Оставляем только целые неотрицательные количества. Это необходимые и достаточные условия: сами найденные блоки образуют требуемую сумму. Если строка количеств приведена, это пример; если список пуст, условий не удовлетворяет ни одно разбиение.
T=113T=113
n=50n=50
пример=((36;7;0;0))\text{пример}=\left(\left(36;7;0;0\right)\right)
Шаг 3. Да. Приведённые целые значения удовлетворяют доказанным ограничениям и дают допустимый пример.
Шаг 1. Если сумма не превосходит 9999, блок из пяти единиц невозможен: 11111 уже больше суммы, а все слагаемые положительны. Поэтому достаточно блоков 1, 11, 111 и 1111. Их количества обозначим x1x_{1}, x2x_{2}, x3x_{3}, x4x_{4}. Тогда число исходных единиц n=x1+2x2+3x3+4x4n=x_{1}+2x_{2}+3x_{3}+4x_{4}, а сумма T=x1+11x2+111x3+1111x4T=x_{1}+11x_{2}+111x_{3}+1111x_{4}. Вычитая, получаем T−n=9x2+108x3+1107x4T-n=9x_{2}+108x_{3}+1107x_{4}.
T=x1+11x2+111x3+1111x4T=x_1+11 x_2+111 x_3+1111 x_4
n=x1+2x2+3x3+4x4n=x_1+2 x_2+3 x_3+4 x_4
Шаг 2. Необходимо, чтобы T−nT-n делилось на 9. Для каждого целого x4x_{4} от 0 до min⁡(n4, T1111)\min\left(\frac{n}{4},\,\frac{T}{1111}\right) и x3x_{3} от 0 до min⁡(n−4x43, T−1111x4111)\min\left(\frac{n-4x_{4}}{3},\,\frac{T-1111x_{4}}{111}\right) из равенства для T−nT-n однозначно находим x2x_{2}, затем x1x_{1}. Оставляем только целые неотрицательные количества. Это необходимые и достаточные условия: сами найденные блоки образуют требуемую сумму. Если строка количеств приведена, это пример; если список пуст, условий не удовлетворяет ни одно разбиение.
T=114T=114
n=50n=50
count=0count=0
Шаг 3. Нет. Доказанные необходимые условия исключают все допустимые варианты.
Шаг 1. Для четырёхзначного результата по-прежнему возможны лишь четыре длины блоков. Для каждого x4x_{4} от 0 до min⁡(n4,9)\min\left(\frac{n}{4{,}9}\right) и x3x_{3} от 0 до n−4x43\frac{n-4x_{4}}{3} величина T=n+9x2+108x3+1107x4T=n+9x_{2}+108x_{3}+1107x_{4} возрастает по x2x_{2}. Поэтому достаточно взять наибольшее целое x2x_{2}, ограниченное оставшимися единицами и неравенством T≤9999T\leq 9999. В таблице для каждого x4x_{4} приведён максимум по всем допустимым x3x_{3}; наибольшая строка даёт глобальный максимум. Отдельно выписываем количества блоков, которые его достигают.
таблица=((0;1787);(1;2777);(2;3776);(3;4676);(4;5666);(5;6665);(6;7565);(7;8555);(8;9554))\text{таблица}=\left(\left(0;1787\right);\left(1;2777\right);\left(2;3776\right);\left(3;4676\right);\left(4;5666\right);\left(5;6665\right);\left(6;7565\right);\left(7;8555\right);\left(8;9554\right)\right)
пример=(0;0;6;8)\text{пример}=\left(0;0;6;8\right)
Шаг 2. Записываем полученный ответ.
95549554

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

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