На доске написано n единиц подряд. Между некоторыми из них расставляют знаки «+» и считают получившуюся сумму. Например, если было написано 10 единиц, то можно получить сумму 136: 1+1+111+11+11+1=136.
а) Можно ли получить сумму 132, если n=60?
б) Можно ли получить сумму 132, если n=80?
в) Для скольких значений n можно получить сумму 132?
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Если сумма не превосходит 9999, блок из пяти единиц невозможен: 11111 уже больше суммы, а все слагаемые положительны. Поэтому достаточно блоков 1, 11, 111 и 1111. Их количества обозначим x1, x2, x3, x4. Тогда число исходных единиц n=x1+2x2+3x3+4x4, а сумма T=x1+11x2+111x3+1111x4. Вычитая, получаем T−n=9x2+108x3+1107x4.
T=x1+11x2+111x3+1111x4
n=x1+2x2+3x3+4x4
Шаг 2. Необходимо, чтобы T−n делилось на 9. Для каждого целого x4 от 0 до min(4n,1111T) и x3 от 0 до min(3n−4x4,111T−1111x4) из равенства для T−n однозначно находим x2, затем x1. Оставляем только целые неотрицательные количества. Это необходимые и достаточные условия: сами найденные блоки образуют требуемую сумму. Если строка количеств приведена, это пример; если список пуст, условий не удовлетворяет ни одно разбиение.
T=132
n=60
пример=((44;8;0;0))
Шаг 3. Да. Приведённые целые значения удовлетворяют доказанным ограничениям и дают допустимый пример.
Шаг 1. Если сумма не превосходит 9999, блок из пяти единиц невозможен: 11111 уже больше суммы, а все слагаемые положительны. Поэтому достаточно блоков 1, 11, 111 и 1111. Их количества обозначим x1, x2, x3, x4. Тогда число исходных единиц n=x1+2x2+3x3+4x4, а сумма T=x1+11x2+111x3+1111x4. Вычитая, получаем T−n=9x2+108x3+1107x4.
T=x1+11x2+111x3+1111x4
n=x1+2x2+3x3+4x4
Шаг 2. Необходимо, чтобы T−n делилось на 9. Для каждого целого x4 от 0 до min(4n,1111T) и x3 от 0 до min(3n−4x4,111T−1111x4) из равенства для T−n однозначно находим x2, затем x1. Оставляем только целые неотрицательные количества. Это необходимые и достаточные условия: сами найденные блоки образуют требуемую сумму. Если строка количеств приведена, это пример; если список пуст, условий не удовлетворяет ни одно разбиение.
T=132
n=80
count=0
Шаг 3. Нет. Доказанные необходимые условия исключают все допустимые варианты.
Шаг 1. Здесь T<1111, поэтому x4=0. В равенстве T=x1+11x2+111x3 перебираем x3 от 0 до 111T и x2 от 0 до 11T−111x3; x1 равен остатку и неотрицателен. Получаем n=T−9x2−108x3. Ни одно разбиение не пропущено: его количества блоков входят в эти границы. Удаляем повторяющиеся значения n и считаем оставшиеся.