"Простое" сложение

[Юляша]

Доказательство для четырех сложений

Лемма 1. Частное от деления трехзначного числа (с ненулевой первой цифрой) на сумму его цифр больше 10. (доказывается легко)
Лемма 2. Для чисел от 1 до 118 требуемое число сложений не более двух. (достаточно складывать однозначные числа)

Пусть сумма цифр заданного числа больше чем 10^n и меньше, чем 10^(n+1). Без ограничения общности можно считать, что сумма больше чем 10^n+18, а n>=2 - в противном случае хватит двух сложений (см. лемму 2).

Разобьем исходное число на группы по три цифры слева направо. Если получившееся трехзначное число вдруг будет начинаться с 0, то мы пропускаем все такие нули и начинаем следующую группу с первой ненулевой цифры. В конце у нас может остаться меньше трех цифр, представим их как однозначные числа, их сумма не более 18.

Сумма всех трехзначных чисел с учетом леммы 1 больше, чем 10^(n+1). Начнем "разбирать" трехзначные числа на однозначные слева направо, пока сумма не станет меньше, чем 10^(n+1). После этого соберем последнее трехзначное число обратно. Сумма имеющихся на данный момент чисел лежит в диапазоне от 10^(n+1), до 10^(n+1)+971, а сумма цифр такого числа не превосходит 27.

Соответственно, требуется еще не более 3 сложений (в частности, я не вижу способа справиться с числом 100...00189, полученным после первого шага, за два сложения).

Правда, свободы "переиграть по-другому" остается очень много. И в любом случае, без ограничения общности, можно считать, что остаток от деления исходного числа на 9 равен 1 (для всех остальных чисел трех сложений точно хватает).

[Dendr]

число у нас произвольное. Складывать нам можно же не только цифры, но и числа?
то есть
139
можно сложить и как 1+3+9
и как 13+9
и как 1 + 39

я правильно понимаю?

Можно. Если бы только цифры, то из-за чего весь сыр-бор? (несложно доказать, что можно сконструировать число, которое и за 100 операций сложения только цифр не свернется в однозначное, например, если брать числа вида 11...1 - оно, конечно, безумно длинное, но и задача у нас "сферическая в ваккуме")

[Dendr]

Доказательство для четырех сложений

Хитроумное решение. Ну и, конечно, ответ совпадает с авторским. Но автор решил задачу проще и изящнее, почему мне задача и понравилась.

Начало такое же, только разбиваем исходное на четырехзначные, плюс промежуточные нули и плюс не более трех "лишних" цифр. И конец такой же. Вот доказательство самой серединки на порядок проще, без лишних лемм, хотя принцип все тот же.
1. Легко видеть, что числа из не более, чем 4 цифр (да что там, даже из 11) сворачиваются не более, чем за 3 шага.

2. Разбиваем данное число, как указано выше. Пусть набралось k 4-значных чисел. Их сумма не менее, чем 1000k. Плюс, возможно, "довесок". В любом случае, S1>=1000k

3. Теперь разобьем все числа на отдельные цифры. Получилось максимум 4k+3 цифры, каждая из которых не превосходит 9. То есть, S2<=36k+27. Так как k>=1 (по построению), то 27<=27k<64k.
Таким образом, S2<100k<1000k<=S1.
Например, если k=4127, то S2<412700<4127000<=S1 - в S1 минимум 7 цифр, в S2 - не более 6.

4. То есть, если мы последовательно заменяем четырехзначные числа на сумму их цифр, то в какой-то момент разрядность числа обязательно уменьшилась на один. Так как каждый раз мы вычитаем из общей суммы число, не превышающее 9963 (проверьте!), то в какой-то момент (возможно, в "нулевой" - до замены) промежуточная сумма приобрела вид 10..0abcd, причем число abcd<9963. Оно и будет стартовой точкой для следующего этапа.

5. Ну а число 10..0abcd эквивалентно пятизначному (почти - мы не можем сформирвать число 1ab), которое свернется в однозначное еще за три шага.

Итого - за 4 операции для любого наперед заданного натурального числа мы свернем это число до однозначного.

[Юляша]

Это было бы хорошо, но у меня есть уверенность, что и трех сложений достаточно. Постараюсь дожать.

Идея дожимания основана на том, что минимальный "сверхлимит" не 18, как указано в моем доказательстве, а 188, а значит у меня есть запас как минимум из 20 уже не троек, а пар цифр, которые можно использовать для того, чтобы превратить плохой остаток в хороший.

[Dendr]

Доказать это непросто. Вот опровергнуть... То есть надо составить число, которое за 3 приема свернуть нельзя. Очевидно, что сумма его цифр должна быть не меньше 289, иначе просто складываем цифры, а полученное число за два приема сводим и однозначному. Ткнув наобум, выбрал подозрительное число из 89, повторенного 17 раз. Пробные разбиения приводили к числам, которые сами сворачиваются за три приема, но полностью пока не доказал.

[Юляша]

Да, у меня в последнем сообщении ошибка: не 20 пар, а 20 цифр и, значит, только 10 пар. А это, скорее всего, уже не даст гарантий(.

89 и 98 по 17 раз по моему алгоритму дают, соответственно, 1162 и 1252, то есть, в итоге, складываются за три приема.

[Юляша]

Итак, мы выходим на 4 сложения только если сумма цифр полученного "второго" числа равна 19. Таким образом, возможны следующие числа (точка означает произвольное число нулей).

1.189 1.198
1.279 1.288 1.297
1.369 1.378 1.387 1.396
1.459 1.468 1.477 1.486 1.495
1.549 1.558 1.567 1.576 1.585 1.594
1.639 1.648 1.657 1.666 1.675 1.684 1.693
1.729 1.738 1.747 1.756 1.765 1.774 1.783 1.792
1.819 1.828 1.837 1.846 1.855 1.864 1.873 1.882 1.891
1.909 1.918 1.927 1.936 1.945 1.954 1.963

При этом варианты, выделенные зеленым, укладываются в три действия и могут не учитываться.

Дальше у нас есть 10 резервных пар, каждая из которых позволяет уменьшить получившееся число на значение от 1 до 9 "девяток", в зависимости от первой цифры этого числа. Максимальный запас у нас - 71 "девятка".

Для чисел, выделенных красным, доказательство того, что 10 пар хватит для их приведения к приемлемому виду, несложно. (для нижней из выделенных строк: общее число девяток не более 44, суммы 5 и 6 не должны получаться, следовательно, максимум 4 единицы "в младшей части", а 4 единицы+6 семерок - это уже больше 44.

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

[Юляша]

О! Достаточно проверить только нижнюю строчку таблицы, потому что для элемента, расположенного выше, ограничения такие же, как для нижележащего, но менее жесткие.

Механизм исключения примерно следующий:

Возьмем, например, число 1.882.

Оно придет к приемлемому для нас виду, если мы исключим 8,9,10; 18,19,20,21; 28,29,30,31,32. Дальше пока смотреть не будем.

Таким образом среди первых цифр наших двузначных чисел может быть максимум следующая комбинация: 77665433222 (единички пока не трогаем). Здесь одиннадцать цифр, но комбинации 54 и 332 неприемлемы, а значит, без единичек не обойтись. Но первая единичка потребует убрать семерки, вторая - шестерки. В итоге цифр станет еще меньше, а значит, адекватной подборки не получится. Следовательно, результат 1.882 можно привести к приемлемому для нас виду.

Аналогичным приемом легко убираются все числа нижней строки, кроме двух первых (1.819 и 1.828). Там, в общем-то тоже особых сомнений нет, но ситуация капельку посложнее.

[Dendr]

Я так рассуждаю. (будет много, прошу прощения, выводы отдельно)
Разобьем все числа на классы Pn:
К классу P1 принадлежат все числа, которые можно свернуть за один прием (14, 232, 8000100 и т.п.)
Точнее, существует способ так сделать.
К классу P2, соответственно, за два (73, 199 и т.п.)
К классу P3 - за три (289, 577, ...)
К классу P4 - за четыре.

Заметим, что, к примеру, 121ЄP1 (1+2+1=4), но также можно сделать такой порядок: 12+1=13, 1+3=4. Т.е., в принципе, можн сказать, что 121ЄP2. Но для удобства рассуждений будем считать, что каждое число принадлежит только одному множеству, тогда P5=0, и все выше него тоже.

Обозначим mPn - минимальное число, которое принадлежит Pn. В частности, mP1=10, mP2=19, mP3=289.

Промежуточный вывод: допустим, дано число A>=10, и сумма его цифр S.
Если S<10, то AЄP1 (например, 26)
Если SЄP1, то AЄP2 (например, 49)
Если SЄP2, то AЄP3 или AЄP2 (примеры, соответственно: 289, 1099)
Если SЄP3, то... а вот далее подробнее.

Пусть X=mP4. Рассмотрим сумму его цифр S.
Т.к. S<X, то S!ЄP4. ("не принадлежит")
Допустим, SЄP2. Тогда мы из X получим однозначное за три приема - противоречие. (тем более противоречие, если ЄP1) Следовательно, SЄP3.

Возвращаемся к числу X. Расставляя плюсы везде между цифрами и проводя сложение, получаем в итоге S.
Уберем один плюс - это значит, что сумму a+b мы заменили на двузначное ab=10a+b. Cумма теперь равна S'=S+9a.
Важное замечание: должно выполняться условие S'ЄP3.

Следовательно:
Если в X есть хотя бы одна цифра "1" не на месте единиц, то (S+9)ЄP3.
Если "2", (S+18)ЄP3
...
Если "9", (S+81)ЄP3.
Поэтому числа с S=289 - точно не годятся.
Возьмем, допустим, S=739. В числе X могут быть цифры 1, 2, 3, 4, 5 (а вот шестерок и выше быть не может - тогда S'=793ЄP2: 7+93=100, 1+0+0=1 - три приема для X). В разряде единиц может быть и девятка, не суть важно. Разобьем в уме число X на двузначные (включая "числа" вида 0a, а вот числа вида "00" не учитываем), пусть их вышло M. Сумма цифр каждого двузначного не превышает 10, то есть S<=10M+9,
730<=10M; M>=73.
Заметим, что среди этих M чисел может быть не более 5 начинающихся с единицы; не более 2, начинающихся с двойки; максимум одно, начинающееся с тройки. Если в наборе есть хотя бы два числа, начинающихся с 4, то, выбрав расстановку плюсов так, что мы оставим их, как двузначные, а все остальное - однозначные, то S''=S+36+36=811, а оно сворачивается за два приема. Для двух пятерок - аналогично, S''=820.
Не обращая внимания уже на другие возможности, видно, что в нашем наборе не может быть больше, чем 5+2+1+1+1=10 чисел. То есть, по крайней мере 63 из них имеют вид "0a" подвинем набор на один разряд вправо или влево - получится не менее 62 двузначных чисел, начинающихся с ненулевой цифры. Но, как мы знаем, их может быть не более 10. Противоречие.
Следовательно, S(X) не может быть равна и 739.

Рассуждая так и дальше, можно видеть, что если число X существует, то S(X)ЄP3, и (S(X)+9l)ЄP3, где lЄ[1; L], а L - "достаточно" велико.
Насколько достаточно? Заметим, что, по определению L, (S(X)+9*L+9) ЄP2.

Пусть X существует и состоит из K цифр. Отбросим нули и расставим остальные цифры по возрастанию, а потом разделим их на две группы k+k, или k+(k+1). Суммы цифр в каждой из групп обозначим S1 и S2 соответственно. Очевидно, что S1<=S2.
Кроме того, т.к. нулей в наборе нет, что S1>=k
В сумме S=S1+S2 - только однозначные числа. В сумме S' - двузначные (плюс, возможно, одно однозначное). Чтобы минимизировать S', выбираем в разряды десяток только меньшие числа - из первой группы. Тогда минимальная из всех возможных сумм S' равна S'=10*S1+S2.
Точнее, S'>=10*S1+S2, и dS>=9*S1.

Если L<S1, то по крайней мере одна сумма S'>S+9L, то есть S'ЄP2 - противоречие.
Следовательно, L>=S1>=k.
То есть, L по крайней мере не меньше, чем половинное количество ненулевых цифр. Количество ненулевых цифр при фиксированной сумме S больше или равно S/9, т.е. k>=S/18.
Итого, получаем, что если X - существует, то сумма его цифр SЄP3, и все числа вида S+9l (где l<=S/18) тоже ЄP2.

А поскольку, ко всему прочему, мы можем формировать 3-значные числа и более, то рамки для l раздвигаются еще больше...
Вывод - в следующем сообщении, для общего удобства.

[Dendr]

Вывод:
Если существует такое число X (с суммой цифр S), которое не сворачивается указанным образом в однозначное за 3 приема (то, что оно обязательно свернется за 4, уже доказано), то должно, как минимум, выполняться следующее условие:
S - сворачивается за три приема и не сворачивается за 2 (т.н. класс P3).
S+9 - аналогично.
Вообще, все числа вида S+9l (где l - натуральное) и меньшие 3S/2, принадлежат классу P3.

То есть такой набор (S, S+9, S+18, ... ) должен существовать. Вот если бы можно было доказать, что такого не существует... Перебирать вручную утомительно, а составить программу "расставить числа по классам" - не уверен, что она сработает верно.

[Юляша]

Трех сложений достаточно.

Идея из моего последнего сообщения легко доводится до конца.