На доске написано n единиц подряд. Между некоторыми из них расставляют знаки « + » и считают получившуюся сумму. Например, если было написано 10 единиц, то можно получить сумму 136: 1+1+111+11+11+1=136.
а) Можно ли получить сумму 113, если n=50?
б) Можно ли получить сумму 114, если n=50?
в) Какую наибольшую четырёхзначную сумму можно получить, если n=50?
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 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=113
n=50
пример=((36;7;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=114
n=50
count=0
Шаг 3. Нет. Доказанные необходимые условия исключают все допустимые варианты.
Шаг 1. Для четырёхзначного результата по-прежнему возможны лишь четыре длины блоков. Для каждого x4 от 0 до min(4,9n) и x3 от 0 до 3n−4x4 величина T=n+9x2+108x3+1107x4 возрастает по x2. Поэтому достаточно взять наибольшее целое x2, ограниченное оставшимися единицами и неравенством T≤9999. В таблице для каждого x4 приведён максимум по всем допустимым x3; наибольшая строка даёт глобальный максимум. Отдельно выписываем количества блоков, которые его достигают.