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

[Dendr]

На такую замечательную задачку набрел. Решить так и не смог, подглядел в ответ - но это настолько красиво, что не смог устоять и перенести сюда.
Чтобы не было соблазна искать, видоизменю условие.

На доске написано некое натуральное число.
Разрешается расставить знаки "плюс" в любых местах, исходя из здравого смысла, после чего сложить полученные сегменты, как обычную сумму, которую записать ниже.
С новым числом позволяется провести аналогичные действия с теми же правилами.

Вопрос: сколько таких операций (расстановка плюсов и сложение) достаточно провести, чтобы получить в итоге однозначное число?

[team55]

размер доски считаем конечным?

[Dendr]

размер доски считаем конечным?

Конечным. Но... любым.

[Юляша]

Не верится в легкое решение и простой ответ...

10 - первое число, для которого требуется одно сложение;
19 - первое число, для которого требуется два сложения;
199 - первое число с суммой цифр 19, но для него также хватает двух сложений (1+99 -> 1+0+0);
поэтому 289 - первое число, для которого требуется три сложения;
следующая граница - уже 33-значное (как минимум) число, которое тоже еще выстроить надо...

[Белая Волка]

ответ - верхняя граница, подходящая для любого натурального числа?

[Юляша]

ответ - верхняя граница, подходящая для любого натурального числа?

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

[Dendr]

ответ - верхняя граница, подходящая для любого натурального числа?

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

[Юляша]

Было бы интересно доказать, что существует такое n, что число повторов не больше n для любого заданного числа. Если это так, то n, скорее всего, не так уж велико, вероятно от 4 до 6.

Для начала предположим, что заданное число состоит из одних девяток. Поставим себе задачу получить число вида 108, 1008, 10008 и т.д. или максимальное близкое к такому (чтобы нулей было побольше). Есть ли возможность этого добиться?

[Dendr]

Подсказка:
Если мы каким-то образом расставили плюсы "внутрь" числа на некотором этапе, просуммировали, а затом решили добавить еще плюсов, то это считается все еще одной операцией.

[Юляша]

Подсказка:
Если мы каким-то образом расставили плюсы "внутрь" числа на некотором этапе, просуммировали, а затом решили добавить еще плюсов, то это считается все еще одной операцией.

У меня полностью исчезло понимание, что мы делаем

[Dendr]

Запутал, выходит?..

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

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

Собственно вот это и имел в виду: добавление плюсов считается все еще одной и той же операцией.

[Юляша]

Запутал, выходит?..

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

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

Собственно вот это и имел в виду: добавление плюсов считается все еще одной и той же операцией.

То, что можно пробовать несколько разных разбиений и выбирать из них "оптимальное", как бы не вызывало особых сомнений.

Кстати, насчет девяток идея оказалась подозрительной - любое число из одних девяток "складывается" за две операции, так же как произвольное число вида х99.....99 или 99...99х.

Но сама концепция числа, содержащего в себе "почти одни нули" или (как теперь ясно) "почти одни девятки", выглядит плодотворной. Пусть мы хотим путем допустимых операций получить число максимально близкое к 10^n. Изначально неясно, как выбирать n, хотя верхняя и нижняя граница очевидны. Также пока не знаю, насколько близко можно подойти к нужному числу. Будем думать дальше.

[Dendr]

Вот такой очень сильный хинт, в развитие предыдущего (мелким цветным шрифтом, для чистоты):
-->По сути, что есть замена, допустим, 3472421 на 3+4+7+2+4+2+1?<--
Ответ, конечно, очевиден, но это, де-факто, ключевой момент для решения.

[Юляша]

Абсолютно строгого доказательства у меня еще нет, но практически полная уверенность, что трех сложений должно быть достаточно для любого числа уже фактически сложилась. При этом на первом этапе используются не более чем трехзначные числа.

---
Четырех сложений достаточно, для трех осталось чуть-чуть усилить доказательство.

[Белая Волка]

Кстати, насчет девяток идея оказалась подозрительной - любое число из одних девяток "складывается" за две операции, так же как произвольное число вида х99.....99 или 99...99х.

вообще говоря - любую комбинацию цифр можно либо сгруппировать как несколько сумм равных 9 (или 10) и однозначное число
139
1+3+9 = 13
1+3 = 4

либо
567
5+6+7 = 18
1+8 = 9

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

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