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

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

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

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

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

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

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

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

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

  5. Ответ: да

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

  6. Ответ: нет

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

  7. Все возможные количества единиц

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

  8. Ответ

    Сначала: Все возможные количества единиц

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

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

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

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

в) Для скольких значений nn можно получить сумму 132?

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

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

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

Шаг 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=132T=132
n=60n=60
пример=((44;8;0;0))\text{пример}=\left(\left(44;8;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=132T=132
n=80n=80
count=0count=0
Шаг 3. Нет. Доказанные необходимые условия исключают все допустимые варианты.
Шаг 1. Здесь T<1111T<1111, поэтому x4=0x_{4}=0. В равенстве T=x1+11x2+111x3T=x_{1}+11x_{2}+111x_{3} перебираем x3x_{3} от 0 до T111\frac{T}{111} и x2x_{2} от 0 до T−111x311\frac{T-111x_{3}}{11}; x1x_{1} равен остатку и неотрицателен. Получаем n=T−9x2−108x3n=T-9x_{2}-108x_{3}. Ни одно разбиение не пропущено: его количества блоков входят в эти границы. Удаляем повторяющиеся значения nn и считаем оставшиеся.
T=132T=132
F=(15;24;33;42;51;60;69;78;87;96;105;114;123;132)\mathcal F=\left(15;24;33;42;51;60;69;78;87;96;105;114;123;132\right)
Шаг 2. Записываем полученный ответ.
1414

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

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